DSA Tracker

Visualize

Maximum XOR of Two Numbers in an Array

Insert every number's bits into a trie, then greedily flip bits to find its best partner

time O(31n) ≈ O(n)space O(31n) ≈ O(n)

The highest set bit dominates a number's value more than every lower bit combined, so the best partner for a number is whichever other number disagrees with it as high up as possible. Storing every number's binary form in a 2-child trie lets a query greedily step toward the OPPOSITE bit at each level whenever that branch exists, which is exactly how to build the largest possible XOR one bit at a time. 5 and 25 (00101 and 11001) disagree on every single bit, so tracing just those two shows the full algorithm: they build separate branches, and querying 5 walks straight down 25's branch for the maximum possible result, 28.

Details

Animated on: Given nums = [3, 10, 5, 25, 2, 8], find the maximum XOR of any two numbers in the array.

Problem:Maximum XOR of Two Numbers in an ArrayMedium

Insert every number's bits into a trie, then greedily flip bits to find its best partner

step 1 / 9

•

Every value in nums gets inserted into a trie of its 5-bit binary form, most significant bit first. Start with just a root.

Pseudocode
1FUNCTION insert(root, num):
2  node <- root
3  FOR b FROM 4 DOWNTO 0:
4    bit <- BIT(num, b)
5    IF node.children[bit] = NULL: node.children[bit] <- NEW NODE
6    node <- node.children[bit]
7  node.end <- TRUE
8FUNCTION bestPartner(root, num):
9  node <- root, ans <- 0
10  FOR b FROM 4 DOWNTO 0:
11    bit <- BIT(num, b), want <- 1 - bit
12    IF node.children[want] != NULL: ans <- 2*ans + 1, node <- node.children[want]
13    ELSE: ans <- 2*ans, node <- node.children[bit]
14  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Every value in nums gets inserted into a trie of its 5-bit binary form, most significant bit first. Start with just a root.
  2. insert(5): 5 in binary is 00101. No node existed yet, so all 5 bits create a brand-new chain, and the last node is marked as an END (it stores the value 5).
  3. insert(25): 25 in binary is 11001. Its very first bit (1) already differs from 5's first bit (0), so 5 and 25 share NO prefix at all — 25 grows an entirely separate branch off the root.
  4. bit 4 of 5 is 0, so the opposite bit 1 is what we want. A child for 1 exists — follow it. Running XOR so far: 1 (decimal 1).
  5. bit 3 of 5 is 0, so the opposite bit 1 is what we want. A child for 1 exists — follow it. Running XOR so far: 11 (decimal 3).
  6. bit 2 of 5 is 1, so the opposite bit 0 is what we want. A child for 0 exists — follow it. Running XOR so far: 111 (decimal 7).
  7. bit 1 of 5 is 0, so the opposite bit 1 is what we want, but no child for 1 exists here. Fall back to the only link available (bit 0). Running XOR so far: 1110 (decimal 14).
  8. bit 0 of 5 is 1, so the opposite bit 0 is what we want, but no child for 0 exists here. Fall back to the only link available (bit 1). Running XOR so far: 11100 (decimal 28).
  9. The walk ends on the END node for 25 — every level found (or fell back to) a real link, so this is a genuine pair. 5 XOR 25 = 28, matching the trie's own answer of 28. Querying every number the same way and keeping the largest result is the whole algorithm.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximum XOR of Two Numbers in an Array in the editorAll Trie problemsBack to roadmap