Bob was experimenting with an array of numbers in an effort to make a programming problem, finally he made an interesting problem but he cannot solve it, can you help Bob?
Given an array \(A\) of \(n\) integers, Bob wants you to answer \(q\) different queries based on the given array. For each query Bob wants to know the minimum number of values he should remove from the array \(A\) to make the \(XOR\) of the remaining values in the array equal to \(x\).
NOTE: The \(XOR\) of an empty array is \(0\).
Reference: Bitwise XOR
INPUT FORMAT
The first line of the input contains an integer \(n\) (\(1 <= n <= 10^5\)) - the number of values in the array.
The second line of the input contains \(n\) integers \(a_{1}, a_{2}, a_{3}, .. a_{n}\) \((1 <= a_{i} <= 200)\) - the values in the array.
The third line of the input contains an integer \(q\) (\(1 <= n <= 10^5\)) - the number of queries.
Each of the next \(q\) lines contains one integer \(x_{i}\) \((0 <= x_{i} <= 200)\) - the queried value.
OUTPUT FORMAT
Print \(q\) integers. The \(i^{th}\) integer should represent the minimum number of values to remove from \(A\) to make the \(XOR\) equal to \(x_{i}\), or \(-1\) if it is impossible.
In the sample input, \(A = [13, 17, 2, 50, 55]\) and there are \(4\) queries:
For the first query \(x = 46\), removing \(2\) & \(55\) from \(A\) gives you an array \([13, 17, 50]\) with a total \(XOR\) of \(46\). Hence, the answer for the first query is \(2\). It can be shown that you can't make the \(XOR\) equal to \(46\) with less than \(2\) removals.
Likewise, For the second query \(x = 22\), removing \(13\) from \(A\) gives you an array \([17, 2, 50, 55]\) with a total \(XOR\) of \(22\). The answer to this query is \(1\).
For the third query, removing all the \(5\) values in the array gives an array with \(XOR\) as \(0\), and it is the optimal solution.
In the fourth and final query, it is not possible to remove values to make the \(XOR\) of the array equal to \(200\), so the answer is \(-1\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor