algorithm - maximum value of xor operation

Question

I came up with this question.

There is an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers x₁, x₂, ... x_n as key. To implement this algorithm efficiently, Xorq needs to find maximum value for (a xor x_j) for given integers a, p and q such that p <= j <= q. Help Xorq to implement this function.

Input

First line of input contains a single integer T (1<=T<=6). T test cases follow.

First line of each test case contains two integers N and Q separated by a single space (1 <= N <= 100,000; 1 <= Q <= 50,000). Next line contains N integers x₁, x₂, ... x_n separated by a single space (0 <= x_j < 215). Each of next Q lines describe a query which consists of three integers a_i, p_i and q_i (0 <= a_i < 215, 1<= p_i <= q_i <= N).

Output

For each query, print the maximum value for (a_i xor x_j) such that p_i <= j <= q_i in a single line.

Sample Input

1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

Sample Output

13
1016
41
191
191
15
107
47

Explanation

First Query (10 6 10): x6 xor 10 = 12,
    x7 xor 10 = 13, x8 xor 10 = 2, x9 xor 10 = 3, x10 xor 10 = 0,
    therefore answer for this query is 13.
Second Query (1023 7 7): x7 xor 1023 = 1016,
    therefore answer for this query is 1016.
Third Query (33 5 8): x5 xor 33 = 36, x6 xor 33 = 39,
    x7 xor 33 = 38, x8 xor 33 = 41, therefore answer for this query is 41.
Fourth Query (182 5 10): x5 xor 182 = 179,
    x6 xor 182 = 176, x7 xor 182 = 177, x8 xor 182 = 190,
    x9 xor 182 = 191, x10 xor 182 = 188,
    therefore answer for this query is 191.

I tried this by first making the numbers length(in binary) in the given range equal and then comparing 'a' bit by bit with the particular xj values.But it is time exceeding. Maximum time limit in java is 5sec.

Answer 1

I haven't gone through your code in detail, but you seem to have loops over the range of r = p - 1; r < q - 1; r++, and it would be nice not to have to do this.

Given ai, we want to find a value of xi in the given range with as many of its top bits the inverse of ai as possible. Everything is between 0 and 2^15, so there aren't many bits to worry about. For n = 1 to 15 you could divide the xi up according to its n highest bits, so dividing it into 2, 4, 8, 16.. 32768 portions. For each portion keep a list in sorted order of the positions where each possible value is found, so for the top bit you will have two lists, one giving the positions at which the bit pattern is 0.............. and one giving the position at which the bit pattern is 1............ For each triple, you can use binary chop on a particular portion to find if there are any positions within your range at which the top n bits have the bit pattern you are looking for. If they do, fine. If not you will have to accept that one of the xor positions is 0 and slightly modify the pattern you look for with one more top bit set.

The setup cost is 15 linear passes over the xi, which is probably less time than it takes you to read it in. For each line you could do 15 binary chops to see which values of xi match in the top n bits, and modify the pattern of top bits you look for if you can't match a particular bit.

I think your program would be clearer if you separated the I/O from the problem code by making the problem code a separate subroutine. This would also make it easier to compare one version of the problem code with another, to see which is faster and if they both get the same answer.