Maximum XOR With an Element From Array

The basic idea is to iterate over the array ‘ARR’ for each query. For the ith query i.e ‘QUERIES[i]’, we iterate over ‘ARR’ and find the xor of ‘Xi’ with every integer in ‘ARR’ smaller or equal to ‘Ai’, If every integer in ‘ARR’ is greater than ‘Ai’, then the answer of this query is -1 otherwise, it is maximum xor value.

The steps are as follows:

1. Create an integer array/list ‘RESULT’ of size ‘M’, and initially fill it with -1.
2. Run a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ do the following -:
   1. Run a loop where ‘j’ ranges from 0 to ‘N’-1 and do following -:
      1. If ARR[j] <= QUERIES[i][1] then do ‘RESULT[i]’:= max('RESULT[i]', ‘ARR[j]’ XOR ‘QUERIES[i][0]’) .  (Note, QUERIES[i][0] is Xi, and QUERIES[i][1] is Ai).
3. Return ‘RESULT’.

The basic idea is to sort the given array ‘ARR’ in non-decreasing order.  Then for each query maintains two pointers ‘LEFT’, ‘RIGHT’, such that the integer that gives maximum xor with Xi is an index in the range [LEFT, RIGHT).

Now for each query ‘i’,  We enumerate over bits of ‘Xi’  from MSB (Most significant bit) to LSB (Least significant bit),   For each position of bit, if the bit of ‘Xi‘ in that position is 0, we try to find an integer with bit 1 in that position in the range [LEFT, RIGHT) of ‘ARR’. We can find it using binary search in O(logN) times and update this range accordingly.  Similarly, if the bit of ‘Xi’  in that position is 1, we try to find an integer with bit 0 in that position in the range [LEFT, RIGHT) of ‘ARR’ and update this range accordingly.

The steps are as follows:

1. Create an integer array/list ‘RESULT’ of size ‘M’, and initially fill it with -1.
2. Sort ‘ARR’ in non-decreasing order.
3. Run a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ do the following -:
   1. Let ‘X’ := QUERIES[i][0]  and ‘A’ := QUERIES[i][1].
   2. If ‘A’ < ARR[0], then skip this iteration as the answer to this query will be -1.
   3. Initialize integer variable ‘LEFT’:= 0, ‘RIGHT’ by upper bound of ‘A’ in ‘ARR’, ‘ANS’:= 0 and ‘CUR’:=0.   (Note -: Upper bound here is the smallest index ‘idx’ in ‘ARR’ such that ‘ARR[idx]’ > ‘A’. You can use an inbuilt library function based on the binary search for it )
   4. Run a loop where ‘j’ ranges from 30 to 0 and do the following -:
      1. If the jth bit is set in ‘X’, then check whether the jth bit is set in ARR[LEFT] or not, if this bit is not set, then set ‘jth’ bit in ‘ANS’, and update ‘RIGHT’ by lower bound of ‘CUR’+(2^j) in subarray ARR[LEFT : RIGHT], Otherwise do, CUR:= CUR + 2^j.  (Note -: Lower bound here is the smallest index ‘idx’ in range [LEFT, RIGHT] such that ‘ARR[idx]’ >= ‘CUR’+(2^j). You can use an inbuilt library function based on the binary search for it ).
      2. If the jth bit is not set in ‘X’, then check whether the jth bit is set in ARR[RIGHT-1] or not, if this bit is set, then set ‘jth’ bit in ‘ANS’,  do, CUR:= CUR + 2^j and update ‘LEFT’ by lower bound of ‘CUR’ in subarray ARR[LEFT : RIGHT], Otherwise do nothing.
   5. Do RESULT[i]:= ANS.
4. Return ‘RESULT’:

The basic idea is to convert each integer in ‘ARR’ in the binary format with exactly 31 bits and construct a trie. Trie here is basically a rooted binary tree where each edge is either labelled by 0 or 1.   We can query maximum bitwise XOR in O(31) times using trie. 

We process ‘QUERIES’ in non-decreasing order of ‘Ai’,   and construct the trie on the fly. Before processing the ‘i-th’ query, we make sure only those integers of ‘ARR’ that do not exceed ‘Ai’ are added to the trie.

The steps are as follows:

1. Create an integer array/list ‘RESULT’ of size ‘M’, and initially fill it with -1.
2. Sort ‘ARR’ in non-decreasing order.
3. Create an integer array/list ‘ORDER’ of size ‘M’ and initially for each 0 <= ‘i’ < ‘M’ do ORDER[i] := i.  This array will give the order in which we should process queries.
4. Sort ORDER such that for any pair (i < j) QUERY[ORDER[i]][1] <= QUERY[ORDER[j][1]]. This can be done easily using comparator in sort function
5. Create an empty Trie.
6. Initialize an integer ‘p’:= 0. It will point at the smallest index, the integer at which is not inserted in the trie.
7. Run a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ do the following -:
   1. Let ‘X’ := QUERIES[ORDER[i]][0]  and ‘A’ := QUERIES[ORDER[i]][1].
   2. Run a loop till p < N and ‘ARR[p]’ <= ‘A’ and insert 31-bit binary format of ARR[p] in the trie.  Note in the trie, the least significant bits should be the leaf.
   3. If Trie is empty, then skip this iteration as the answer to this query will be -1.
   4. Initialize integer ‘ANS’: = 0. Now we find maximum xor for ‘X’ by trie as describe in the following steps.
   5. Keep a pointer ‘ptr’ at the root of the trie.
   6. Run a loop where ‘j’ ranges from 30 to 0 and do the following -:
      1. If the jth bit is set in ‘X’, then check whether there exists an edge labelled with 0 for node pointed by ‘ptr’. If yes then set ‘jth’ bit in ‘ANS’, and move ‘ptr’, to the node followed by this edge, otherwise, move ‘ptr’ to node followed by edge labelled 1.
      2. If the jth bit is not set in ‘X’, then check whether there exists an edge labelled with 1 for node pointed by ‘ptr’. If yes then set ‘jth’ bit in ‘ANS’, and move ‘ptr’, to the node followed by this edge, otherwise, move ‘ptr’ to node followed by edge labelled 0.
   7. Do RESULT[ORDER[i]]:= ANS.
8. Return ‘RESULT’