Maximum XOR of Two Numbers
mediumTime: O(n)Space: O(n)
Signals to notice
maximize XOR of two numbersbinary triegreedy bit choice
Brute force first
XOR every pair — O(n²).
The key insight
Binary trie (MSB to LSB). For each number, walk trie choosing opposite bit at each level. O(32n).
What must stay true
Opposite bits maximize XOR. Trie enables greedy bit-by-bit maximization in O(32) per number.
Easy way to go wrong
Using decimal trie — it's a BINARY trie with 2 children per node.