Maximum XOR of Two Numbers in an Array
Understanding the Problem
We need to pick two numbers from the array (they can be the same element, since i can equal j) and XOR them together, then return the largest XOR result possible across all pairs.
XOR (exclusive or) compares corresponding bits of two numbers. If the bits differ, the result bit is 1. If they match, it's 0. To maximize the XOR, we want two numbers whose binary representations differ in as many high-order bit positions as possible. A 1 in bit position 30 contributes 2^30, which exceeds the sum of 1s in every position from 0 to 29 combined (2^30 - 1). So the strategy is greedy: set the highest bit to 1 first if possible, then the next highest, and so on. That bit-by-bit reasoning drives both optimal approaches below.
Key Constraints:
1 <= nums.length <= 2 * 10^4→ With n up to 20,000, an O(n^2) brute force performs up to 400 million XOR-and-compare operations. That can pass with a fast constant factor, but the better approaches below run in O(n).0 <= nums[i] <= 2^31 - 1→ Values are non-negative 32-bit integers, so bit 30 is the highest bit that can be set, and we only consider bits 30 down to 0. Any approach that iterates over bits multiplies the cost by at most 31.
Approach 1: Brute Force
Intuition
Try every pair. For each pair (i, j), compute nums[i] XOR nums[j] and track the maximum across all pairs. XOR is a single machine instruction, so each of the O(n^2) checks is cheap, and this is enough for small arrays.
Algorithm
- Initialize
maxXor = 0. - For each index
ifrom 0 to n-1, for each indexjfromito n-1, computenums[i] XOR nums[j]. - Update
maxXorif the current XOR is larger. - Return
maxXor.
Example Walkthrough
Code
- Time Complexity: O(n^2). We check every pair of elements. There are n*(n+1)/2 pairs, each requiring O(1) work for the XOR and comparison.
- Space Complexity: O(1). We only use a single variable to track the maximum.
The brute force ignores the bit structure of XOR. The next approach uses it to build the answer one bit at a time, in O(n).
Approach 2: Bitwise Prefix with Hash Set
Intuition
We can build the maximum XOR one bit at a time, from the most significant bit (MSB) down to the least significant bit (LSB). At each bit position we ask whether that bit can be set to 1 in the answer. If yes, we keep it; if no, it stays 0 and we move to the next bit.
To check whether a bit can be set, we use the XOR identity: if a XOR b = c, then a XOR c = b. We work with prefixes, the high bits of each number down to the current bit position. Suppose the candidate answer has prefix candidatePrefix. If two numbers a and b produce it, then a XOR b = candidatePrefix, which rearranges to a XOR candidatePrefix = b. So we store every number's prefix in a hash set, and for each prefix p we test whether p XOR candidatePrefix is also in the set. A match means some pair achieves the candidate.
The greedy order from MSB to LSB is safe because bit k is worth 2^k, which exceeds the combined value of all lower bits (2^k - 1). So whenever bit k can be set, setting it produces a larger answer than any result that leaves it 0, no matter what the lower bits do. Committing to a confirmed high bit never blocks a better overall answer, so the final value is the global maximum.
Algorithm
- Initialize
maxXor = 0. - For each bit position
kfrom 30 down to 0: - Compute
candidate = maxXor | (1 << k), the best answer so far with bit k tentatively set to 1. - Build a hash set of prefixes, one per number:
prefix = num >> k. - Let
candidatePrefix = candidate >> k. For each prefixpin the set, check whetherp XOR candidatePrefixis also in the set. - If a match exists, set
maxXor = candidate(bit k is confirmed reachable). OtherwisemaxXoris unchanged and bit k stays 0. - Return
maxXor.
Example Walkthrough
Code
- Time Complexity: O(31 * n) = O(n). We iterate through 31 bit positions. At each position, we build a set of prefixes (O(n)) and check each prefix against the set (O(n) with O(1) average hash lookups).
- Space Complexity: O(n). The hash set stores at most n prefixes at each bit position.
The hash set approach is O(n) but rebuilds the set 31 times and pays hash overhead on every lookup. The next approach stores all numbers once in a binary trie, then walks it greedily for each number, choosing the opposite bit at every step.
Approach 3: Binary Trie (Optimal in Practice)
Intuition
Represent every number as a 31-bit binary string and insert all of them into a trie where each node branches on a 0 or 1 child. Shared high-bit prefixes share the same path, so the trie compactly holds every number in the array.
To find the best XOR partner for a given number, walk down from the root one bit at a time. Since XOR produces a 1 when bits differ, at each level we take the child for the opposite bit when it exists: if the number has a 0 at bit k, we follow the 1-child, and vice versa. When the opposite child is missing, we follow the same-bit child, which contributes 0 to the XOR at that position. The path traced this way gives the maximum XOR partner for that number in 31 steps.
This greedy choice is optimal for the same reason as Approach 2: bit k is worth 2^k, which exceeds the sum of all lower bits, so taking a 1 at the highest available bit is never worse than any alternative. Repeating the walk for every number and keeping the largest result gives the answer.
Algorithm
- Build a binary trie: for each number in the array, insert its binary representation (31 bits, from MSB to LSB) into the trie.
- For each number in the array, traverse the trie greedily:
- At each bit position (from bit 30 down to 0), check the current bit of the number.
- Try to go to the child with the opposite bit (this maximizes XOR at this position).
- If the opposite child doesn't exist, go to the same-bit child.
- Accumulate the XOR result based on which path was taken.
- Track the maximum XOR across all numbers.
- Return the maximum.
Example Walkthrough
Code
- Time Complexity: O(31 n) = O(n). Inserting n numbers into the trie takes O(31 n). Querying n numbers takes O(31 * n). Total: O(62n) = O(n).
- Space Complexity: O(31 n) = O(n). The trie has at most 31 n nodes, each storing two child pointers. In practice, shared prefixes reduce this.