Problem Statement

Maximum XOR of Two Numbers in an Array

You are given a list of whole numbers called nums. Pick any two of them and combine them with an operation called XOR. XOR compares two numbers bit by bit (a bit is a single 0 or 1, and every number is really just a row of bits). For each position, XOR gives 1 when the two bits are different and 0 when they are the same. Your job is to find the pair whose XOR is the largest, and return that largest value. The slow way is to try every pair, which is O(n^2) (that means the work grows with the square of the list size). The faster way uses a Trie, which is a tree where you walk down one step per bit. Here is the key idea: XOR gives 1 when bits differ, so to make XOR big we want each number to find a partner that has the opposite bit at every position, especially at the front where bits count the most.

mediumTrieBit ManipulationTrieTime: O(n * 32) · Space: O(n * 32)

Signals to notice

maximize XOR of any two numbersbit-by-bit greedy choiceopposite bits preferred

Brute force first

XOR every pair. Checks all pairs without exploiting bit structure. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Build a binary trie (each path is a number's bit representation from MSB to LSB). For each number, greedily traverse the trie choosing the opposite bit at each level to maximize XOR. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

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

Phase 1 - insert all 6 numbers into the binary trie, each as a 32-bit MSB->LSB path. result=0.
Query num=3 (00011): greedy toggle picks complement 25 (11001) -> xor=11010=26. result=max(0,26)=26.
Query num=10 (01010): greedy toggle picks complement 25 (11001) -> xor=10011=19. result=max(26,19)=26.
Query num=5 (00101): greedy toggle picks complement 25 (11001), bits differ at 16,8,4 -> xor=11100=28. result=max(26,28)=28.
Query num=25 (11001): greedy toggle picks complement 5 (00101) -> xor=11100=28. result=max(28,28)=28.
Query num=2 (00010): greedy toggle picks complement 25 (11001) -> xor=11011=27. result=max(28,27)=28.
Query num=8 (01000): greedy toggle picks complement 25 (11001) -> xor=10001=17 (<28). result stays 28.
Return result = 28 (from 5 XOR 25).

What must stay true

To maximize XOR, you want opposite bits at every position (1 XOR 0 = 1). The trie lets you greedily choose the opposite bit at each level — if it exists, take it; otherwise, take what's available. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

insert each num into trie bit-by-bit (i = 31..0, take bit = (num>>i)&1)
result = 0
for each num:
    cur = root; xor = 0
    for i = 31..0: want = 1 - ((num>>i)&1)
        if want in cur.children: xor |= (1<<i); cur = cur[want]   # opposite bit available
        else: cur = cur[1-want]                                   # forced to same bit
    result = max(result, xor)
return result

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

Easy way to go wrong

Building a decimal trie instead of a binary trie — each node has exactly 2 children (0 and 1), representing each bit position from most significant to least. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Trie Pattern