Problem 19.7 · TrieMedium

Maximum XOR of Two Numbers

PatternTrie (Prefix Tree)Bit Manipulation Hash Map Lookup (Complement)

What it teaches: The binary trie: greedy choice of the opposite bit from the top down.

Practise it on judges as “Maximum XOR of Two Numbers in an Array”.

The problem

Return the maximum value of nums[i] XOR nums[j].

Example 1

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28

5 XOR 25.

Constraints

1 ≤ n ≤ 2 × 10⁵
0 ≤ nums[i] ≤ 2³¹ − 1

Pattern clues in the wording

→ Maximise XOR of a pair

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findMaximumXOR(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [3,10,5,25,2,8]	28
2	nums = [14,70,53,83,49,91,36,80,92,51,66,70]	127

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Binary trie · O(31 n)2. Prefix set, bit by bit · O(31 n)

Binary trie

Time O(31 n) Space O(31 n)

Insert each number's bits 30..0 into a trie stored in arrays. Then query: at each bit, move to the opposite bit if it exists (adding that bit to the result), else the same bit.

Approach 1

class Solution {
    public int findMaximumXOR(int[] nums) {
        int[][] next = new int[nums.length * 31 + 1][2];
        int size = 1, best = 0;
        for (int x : nums) {
            int node = 0;
            for (int b = 30; b >= 0; b--) {
                int bit = (x >> b) & 1;
                if (next[node][bit] == 0) next[node][bit] = size++;
                node = next[node][bit];
            }
            int cur = 0, xor = 0;
            for (int b = 30; b >= 0; b--) {
                int bit = (x >> b) & 1;
                if (next[cur][bit ^ 1] != 0) { xor |= 1 << b; cur = next[cur][bit ^ 1]; }
                else cur = next[cur][bit];
            }
            best = Math.max(best, xor);
        }
        return best;
    }
}

Verdict: Linear in n.

Prefix set, bit by bit

Time O(31 n) Space O(n)

Build the answer from the top bit. For each bit, guess it's 1 and check with a hash set of prefixes whether two prefixes XOR to the guess (a ^ b = guess ⇔ a ^ guess = b).

Approach 2

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int b = 30; b >= 0; b--) {
            mask |= 1 << b;
            Set<Integer> prefixes = new HashSet<>();
            for (int x : nums) prefixes.add(x & mask);
            int guess = max | (1 << b);
            for (int p : prefixes) {
                if (prefixes.contains(p ^ guess)) { max = guess; break; }
            }
        }
        return max;
    }
}

Verdict: Same complexity, no trie.

Before you submit

Edge cases and common mistakes

Test these inputs

Single number (answer 0)
All equal numbers

Mistakes people make

Walking from the low bits.
Using 32 bits with signed shifts for non-negative input (bit 31 is the sign).

Interview

Follow-up questions

How do you answer "max XOR of x with any number ≤ m" queries?