We are given two constraint L and R(L<=R) and we have to find two values i and j(l<=i<=j<=R) such that Xor of them is maximum.
I already tried O(n^2) so want anything better.
Here is the solution that you can use (This gives you answer in log(R))
Let me explain it with an example:
Let L=34, R=45. Represent them as bit-arrays:
L = 100010 R = 101101
You start from the left till you find the first mismatch of the form:
L[i] = 0 and R[i] = 1
You will always find this because L < R. (If L==R, this is trivial case and answer is 0)
From here on, change every bit of L to 1 and every bit of R to 0.
The numbers you get will be your i and j and their XOR will be the max you can get.
eg. 34 and 45
100010 and 101101
1st mismatch at index 2 [0-based]
From there, change all L[i] to 1 and all R[i] to 0
=> i = 100111 and j = 101000
=> i = 39 and j = 40
and i^j = 15