Problem Statement

Maximum XOR of Two Numbers

You are given a list of non-negative whole numbers. Pick any two of them and XOR them together. XOR is a way of comparing two numbers bit by bit: at each position, the result bit is 1 when the two input bits are different, and 0 when they are the same. So XOR rewards differences. Your job is to find the pair whose XOR is the largest possible, and return that value. The clever tool for this is a trie. A trie is like a branching tree of choices, the same way a phone keypad word-finder narrows down letter by letter. Here each number is spelled out in its bits, from the biggest bit down to the smallest, and each bit (0 or 1) is one fork in the road. Once every number lives in the trie, we walk it for each number and, at every fork, we try to go the opposite way, because opposite bits give a 1 in XOR, and a 1 in a high position is worth a lot.

mediumBit ManipulationTrieTrieTime: 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).

Trace it on `nums=[3,10,5,25,2,8]`

Build binary trie: insert all 6 numbers bit-by-bit MSB->LSB. 5-wide bits: 3=00011, 10=01010, 5=00101, 25=11001, 2=00010, 8=01000
Query num=3 (00011): greedy opposite-bit walk -> diverges toward 25's high bits, curr=11010=26 (3 XOR 25). best=26
Query num=10 (01010): opposite-bit walk -> best reachable curr=10011=19. best stays 26
Query num=5 (00101): opposite-bit walk finds 25 (11001) path -> curr=11100=28 (5 XOR 25). best=28
Query num=25 (11001): opposite-bit walk finds 5 (00101) -> curr=11100=28. best stays 28
Query num=2 (00010) -> curr=11011=27; num=8 (01000) -> curr=10001=17; both <=28, best unchanged
Return best = 28  (5 XOR 25 = 28)

What must stay true

Opposite bits maximize XOR. Trie enables greedy bit-by-bit maximization in O(32) per number.

Shape of the loop

build trie: for each num, insert its bits MSB→LSB (2 children per node)
best = 0
for num in nums:
  node, curr = root, 0
  for i from high_bit down to 0:
    want = opposite of num's bit i
    if want in node: curr |= (1<<i); node = node[want]   # took divergent path
    else:           node = node[num's bit i]
  best = max(best, curr)
return best

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using decimal trie — it's a BINARY trie with 2 children per node.

Trie Pattern