Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Perfect Collection

Limits: 1s, 512 MB

Given an array A of N integers, if we choose any K of these integers and calculate their bitwise XOR, what is the minimum possible result that we can get?

A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For more detail, visit Wikipedia


The first line of the input contains two integers, N (1 ≤ N ≤ 102) and Q (1 ≤ Q ≤ 103), the size of the given array and the number of queries .

The next line contains N space separated integers, the elements of the array A (1 ≤ Ai ≤ 103).

The next Q lines contain one integer each. ith of these integers represents the value of K (1 ≤ K ≤ N) for the ith query.


For each query, print one integer in a separate line: the minimum possible bitwise XOR value of any K integers of the given array.


4 2
2 5 7 4


For the first query, the possible choices here are: (2,5), (2,7,), (2,4), (5,7), (5,4), (7,4). Among these, the bitwise XOR of (5,4) yields 1 which is the minimum of all the six possible results.

For the second query, 2 is minimum value in the given array.

  • Labib666's Avatar


    Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms.

Login to submit


Login to unlock editorial