For example, our range is from l=3(0011) to r=15(1111) and our x=1(0001), we will know that by its binary representation max xor(i.e, y) will only lie in range between l’=1000 and r=1111. In this way I’m trying to solve this bit by bit(taking from left to right). But I’m not getting how to shrink the ranges. Can someone explain how to achieve this? Or is there any better way to do this question?
Your approach is correct. Your first try to maximise the most significant bit, then subsequently smaller and smaller ones.
To maximise the j th bit of X^Y, Y’s jth bit has to be different from X’s.
When counting up from 0, j th bit changes every 2^j steps, so we can shrink the range as follows: Let the current range be L, R and M be the first multiple of 2^j in the range. If there is no such M, let it say L, R. If there is exactly 1 multiple of 2^j in the range, shrink the range to L, M-1 or M, R depending on which bit you want.
Otherwise, consider the ranges M, M+2^j-1 and M+2^j, M+2^j*2-1 which lie in our range ( the second one may not) . If one of these ranges contains the required j th bit, shrink to that one instead of L, M-1 or M, R because this will help maximise the bits after the j th one.
However I don’t think it’s possible to get a case where there is more than 1 multiple of 2^j in the range
1 Like