Maximum XOR of Two Numbers in an Array
Pick two numbers from the array maximizing a XOR b — in better than O(n²).
Intuition
XOR is maximized bit by bit from the top: a high differing bit beats all lower bits combined. Store every number's 32-bit path in a binary trie (0/1 children). For each number, walk the trie greedily choosing the opposite bit whenever that branch exists — that partner maximizes the XOR with this number. Best over all numbers is the answer.
A bitwise trie over 32-bit numbers. XOR is maximised bit by bit from the top: at each level, greedily follow the opposite bit if that branch exists, because setting a high bit outweighs everything below it. Storing numbers as bit-paths is what makes "is there a number with the opposite bit here?" an O(1) lookup.
Approach
Why brute force wastes work
All pairs is O(n²). But the best partner for a number is determined greedily per bit — high bits dominate — so a per-bit index (the trie) finds it in 32 steps.
Build the bit trie
Insert each number as its 32-bit path, most significant bit first. Nodes are {0:…, 1:…} dicts.
Greedy opposite walk
For each num, from the top bit down: prefer the child with the flipped bit (sets this XOR bit to 1); fall back to the same bit. Accumulate the XOR value; track the global max.
Solution & live demo
Common pitfalls
Comparing every pair
return max(a ^ b for a in nums for b in nums)
for i in range(31, -1, -1):
want = 1 - b
if want in cur: ...O(n²) times out at n = 200,000. The trie answers "what is the best partner for this number?" in 32 steps regardless of how many numbers there are.
Iterating bits from least significant upward
for i in range(32):
for i in range(31, -1, -1):
The greedy only works top-down: securing bit 30 is worth more than every lower bit combined. Starting from the bottom makes early choices that a later high bit can't justify.
Not falling back when the opposite branch is missing
if want in cur:
xor_val |= (1 << i); cur = cur[want]if want in cur:
xor_val |= (1 << i); cur = cur[want]
elif b in cur:
cur = cur[b]If no stored number has the opposite bit, the walk must continue down the same-bit branch — that bit simply contributes 0. Without the fallback cur goes stale and every deeper comparison is meaningless.
Edge cases
Opposite branch never exists — XOR 0.
Pairs with itself → 0 (insert-then-query order makes this safe).
Zero's best partner is simply the max element.