Problem Statement
You are given the int[] a of length 2*n. This array contains each of the integers 1 through n exactly twice.
A removal is the following action:
- choose two indices i and j such that j-i is odd and a[i] = a[j]
- delete a[i] and a[j] from the array
- concatenate the remaining parts of a into a shorter array
- You may pick i = 1, j = 4 to remove both occurrences of the integer 2 and obtain the new array {1, 4, 1, 3, 4, 3}.
- You may not pick i = 1, j = 2, as a[i] != a[j].
- You may not pick i = 2, j = 6, as j-i is even.
You may perform zero or more removals, with the additional constraint that the removed values must be strictly increasing.
Return the long[] res of length n+1, where res[i] is the number of ways to remove exactly i pairs of integers from a.
Definition
- Class:
- OddPairRemoval
- Method:
- waysToRemove
- Parameters:
- int[]
- Returns:
- long[]
- Method signature:
- long[] waysToRemove(int[] a)
- (be sure your method is public)
Constraints
- n will be between 1 and 52, inclusive.
- The length of a will be exactly 2*n.
- Each integer between 1 and n, inclusive, will have exactly two occurrences in a.
Examples
{1, 2, 1, 3, 2, 3}Returns: {1, 1, 1, 0 }We have the following options: We don't remove anything. We remove the 2s and then stop. We remove the 2s, producing the array {1, 1, 3, 3}, and then we remove the 3s. There is 1 way to remove no pairs, 1 way to remove one pair, 1 way to remove two pairs, and 0 ways to remove all three pairs. Therefore, the correct return value is {1, 1, 1, 0}. Note that in the beginning we cannot remove the 1s because their distance is even. Once we remove the 2s, the distance between the 1s becomes odd. However, now we cannot remove them due to the additional constraint that removed values must be increasing.{1, 2, 3, 1, 2, 3}Returns: {1, 3, 0, 0 }We can remove any number. Afterwards, all the other pairs will be at even distance and further removal will be impossible.{1, 1, 2, 2, 3, 3, 4, 4}Returns: {1, 4, 6, 4, 1 }The numbers are independent, hence any subset can be removed.{2, 3, 1, 6, 2, 5, 3, 7, 4, 1, 4, 7, 5, 6}Returns: {1, 3, 5, 6, 6, 6, 4, 1 }