Problem Statement
One day, Frederica found the int[] num that consisted of N non-negative integers.
She thinks that only sorted arrays are beautiful, so she would like to transform num into a sequence that is sorted in strictly ascending order.
However, she thinks that simply sorting the elements is not fun. Instead, she is going to do the following operation:
- First, she picks some integer A that is between 0 and 2^30 - 1, inclusive.
- Second, she will xor all elements of num with the chosen A. That is, the new value of num[i] will be (num[i] xor A), for all valid i.
Of course, not every selection of A makes the final sequence sorted.
In order to help Frederica, please calculate and return the number of different choices for A that do change num into a sequence in strictly ascending order.
Definition
- Class:
- CapriciousSorting
- Method:
- count
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int count(int[] num)
- (be sure your method is public)
Constraints
- N will be between 2 and 50, inclusive.
- num will contain exactly N elements.
- Each element in num will be between 0 and 2^30 - 1, inclusive.
Examples
{0, 1, 2, 3, 4, 5, 6, 7}Returns: 134217728
We can choose the highest 27 bits of A arbitrarily. The lowest three bits of A must be 0.{7, 6, 5, 4, 3, 2, 1, 0}Returns: 134217728
Again, we can choose the highest 27 bits of A arbitrarily. This time the lowest three bits of A must be 1.{47, 47, 42}Returns: 0
Regardless of which A you choose, the first two elements will always be the same and thus the sequence will never be strictly increasing.{84, 94, 68, 72, 96, 31, 2, 57}Returns: 67108864