Store each number as a 32-bit binary string in the trie. Each node has at most 2 children: 0 and 1.
For XOR, you want corresponding bits to differ. When finding the maximum XOR partner for a number:
- At each bit, try to go the opposite direction
- If opposite doesn't exist, go the same direction
- Build the XOR result bit by bit
function findMaxXOR(num, root):
node = root
xor = 0
for i from 31 down to 0:
bit = (num >> i) & 1
oppositeBit = 1 - bit
if node.children[oppositeBit]:
xor |= (1 << i)
node = node.children[oppositeBit]
else:
node = node.children[bit]
return xor
Process from most significant bit to least significant. Higher bits contribute more to the result.