Make Xor | HackerEarth

Make Xor

Practice

4.7 (3 votes)

Algorithms

2d dynamic programming

Bit manipulation

Dynamic programming

Problem

76% Success 448 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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.

Sample Input

5
13 17 2 50 55
4
46
22
0
200

Sample Output

Explanation

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\).

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor