Pattern visualizer

Maximum XOR of Two Numbers in an Array

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. Animated on: Given nums = [3, 10, 5, 25, 2, 8], find the maximum XOR of any two numbers in the 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)step 1 / 9

•

line 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.

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

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap