Problem Statement
You are given an int k and a int[] a of length n. The value k is positive. Each element of a is between 0 and (2^k)-1, inclusive.
Your task is to find int[]s b and c with the following properties:
- b and c must contain n elements each
- each element of b and c must be between 0 and (2^k)-1, inclusive.
- the elements of b must be distinct
- the elements of c must be distinct
- for each valid i, a[i] must be equal to (b[i] xor c[i]).
If there is no such b and c, return {-1}. (I.e., a int[] with a single element that is -1.) Otherwise, return a int[] with 2n elements: the concatenation of b and c. If there are multiple valid solutions, you may return any of them.
Definition
- Class:
- XorPuzzle
- Method:
- find
- Parameters:
- int, int[]
- Returns:
- int[]
- Method signature:
- int[] find(int k, int[] a)
- (be sure your method is public)
Constraints
- k will be between 1 and 10, inclusive.
- a will contain between 1 and 2 ^ k elements, inclusive.
- Each element of a will be between 0 and (2 ^ k) - 1, inclusive.
Examples
2
{1, 2, 3}Returns: {2, 3, 1, 3, 1, 2 }One can choose b = {2, 3, 1} and c = {3, 1, 2}. 1 = 2 ^ 3, 2 = 3 ^ 1, 3 = 1 ^ 2.2
{1, 1, 1}Returns: {1, 0, 3, 0, 1, 2 }b = {1, 0, 3}, c = {0, 1, 2}. 1 = 1 ^ 0 = 0 ^ 1 = 3 ^ 2.1
{0}Returns: {0, 0 }b = c = {0}1
{0, 1}Returns: {-1 }There is no answer.5
{1, 18, 27, 30, 16, 30, 2, 19, 21, 30, 13, 20, 0, 25, 27, 31, 26, 23, 2, 11, 5, 31, 16, 10, 21, 21, 25, 4, 29, 24, 21}Returns: {9, 17, 2, 19, 8, 11, 3, 21, 16, 26, 7, 6, 12, 25, 28, 22, 20, 10, 29, 24, 31, 1, 4, 27, 14, 23, 5, 18, 13, 15, 30, 8, 3, 25, 13, 24, 21, 1, 6, 5, 4, 10, 18, 12, 0, 7, 9, 14, 29, 31, 19, 26, 30, 20, 17, 27, 2, 28, 22, 16, 23, 11 }
Back to all problems