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
def findMaxXOR(num, root):
node = root
xor = 0
for i in range(31, -1, -1):
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.