Maximum XOR of Two Numbers

Write max_xor(nums) that returns the largest value of nums[i] ^ nums[j] over all pairs of different positions i and j in the list.

The list can be long, so comparing every pair is far too slow. Think about the answer one bit at a time, starting from the highest: a 1 in a high bit is worth more than all the lower bits put together.

Examples

max_xor([8, 1, 6])             # returns 14
max_xor([25, 10, 36, 3, 17])   # returns 61
max_xor([7, 7])                # returns 0

In the first example, 8 is 1000 and 6 is 0110 in binary, and 8 ^ 6 is 1110, which is 14. In the second, 36 ^ 25 is 100100 ^ 011001 = 111101, which is 61.

Constraints

• 2 <= len(nums) <= 20,000
• 0 <= nums[i] < 2**30