Problem Link :Contest Practice
Given a set of numbers from 0 to n (both inclusive), you have to find a pair of number with
maximum XOR and print the maximum XOR value.
XOR of two bits is 1 if they are different, otherwise it's zero. In order to maximize XOR, we
must ensure that the two numbers have as many bits different at a given position as possible.
Since the list is sequencial and is starting from 0, we cannot have a number whose Most
Significant Bit is higher than that of 'n'. So, we find the positions of 'n' where it is 1, and create a
number with those bits set to zero and vice-versa, i.e.
we find the other number as
Now this number is less than 'n' and is bound to be inside the list.
The XOR of the numbers is 1111111.
From this we can see, the result of the XOR operation is all 1 and where number of 1 is number of
bits in 'n'. If n already contains all 1, we can simply XOR it with 0.
Pseudo code :