Topics › Tries › Problems

Maximum XOR of two numbers in an array

Hard TUF ID 1024 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an array nums of non-negative integers, return the maximum value of nums[i] ^ nums[j] over all 0 ≤ i ≤ j < n, where ^ is bitwise XOR. Allowing i = j means the answer is at least 0, since x ^ x = 0, and a one-element array answers 0. The code also returns 0 for an empty array.

Constraints (LeetCode 421): 1 ≤ n ≤ 2 × 10^5, 0 ≤ nums[i] ≤ 2^31 - 1.

Example 1

nums   = [3, 10, 5, 25, 2, 8]
answer = 28      // 5 ^ 25 = 00101 ^ 11001 = 11100 = 28

Example 2

nums   = [8, 8, 8]
answer = 0       // every pair is equal, and equal numbers XOR to 0

Approach 1: Brute force

Intuition. The answer is the best of all pairs, so try all pairs. XOR is a single instruction, which makes this the fastest possible code per pair, but there are about n^2 / 2 pairs.

Algorithm.

1. Start with best = 0, which covers the i = j case.
2. For every pair i < j, update best = max(best, nums[i] ^ nums[j]).

static int bruteForce(int[] nums) {
    int best = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            best = Math.max(best, nums[i] ^ nums[j]);
        }
    }
    return best;
}

Complexity. Time O(n^2): 2 × 10^5 elements give 2 × 10^10 pairs, far too many. Space O(1).

Approach 2: Optimal, a binary trie with a greedy walk

Intuition. Fix one number x and ask for its best partner. Bit b of x ^ y is 1 exactly when y has the opposite bit to x there. A higher bit outweighs all lower bits together, since 2^b > 2^b - 1 = 2^(b-1) + ... + 1. So the best partner is found greedily from the top: first make bit 30 of the XOR equal to 1 if any number allows it, then, among the numbers that do, make bit 29 equal to 1 if possible, and so on. Giving up a 1 at a high bit to gain 1s lower down can never pay off.

Each step asks: “among the numbers that match every choice so far, does one have the opposite bit here?” Store every number in a binary trie, a trie over the alphabet {0, 1} where each number is its 31 bits from bit 30 down to bit 0. The node reached after some choices holds exactly the numbers matching them, and the question becomes “does this node have the child for the opposite bit?”, an O(1) check. Inputs are non-negative, so bit 31 is always 0 and the trie uses HIGH_BIT = 30.

Algorithm.

1. Insert every number into the trie, highest bit first.
2. For each x, walk from the root with result = 0. At bit b, let want = 1 - bit_b(x). If child[want] exists, set bit b of result and go there; otherwise go to the other child.
3. The answer is the largest result over all x.

static class Node {
    final Node[] child = new Node[2];                  // child[0] for bit 0, child[1] for bit 1
}

static void insert(Node root, int x) {
    Node cur = root;
    for (int b = HIGH_BIT; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (cur.child[bit] == null) cur.child[bit] = new Node();
        cur = cur.child[bit];
    }
}

static int maxXorWith(Node root, int x) {
    Node cur = root;
    int result = 0;
    for (int b = HIGH_BIT; b >= 0; b--) {
        int want = 1 - ((x >> b) & 1);                 // the bit that would make this bit of the XOR 1
        if (cur.child[want] != null) {
            result |= 1 << b;
            cur = cur.child[want];
        } else {
            cur = cur.child[1 - want];
        }
    }
    return result;
}

static int optimalTrie(int[] nums) {
    if (nums.length == 0) return 0;
    Node root = new Node();
    for (int x : nums) insert(root, x);
    int best = 0;
    for (int x : nums) best = Math.max(best, maxXorWith(root, x));
    return best;
}

The “otherwise” branch never meets a missing child. Every stored number has a path of full length 31, so every node above the bottom level has at least one child, and if the preferred one is missing the other must be there.

Dry run of maxXorWith(root, 5) on Example 1. Bits 30 to 5 are 0 in every number, so the walk follows child[0] there without gaining anything. With x = 00101:

maxXorWith(5) = 28. No other x does better: 25 also finds 28, by pairing with 5.

Complexity. Time O(31 · n): each insert and each query visits 31 levels. Space O(31 · n) nodes in the worst case, each with two references. Shared high bits usually save a lot.

Approach 3: Optimal alternative, a hash set of prefixes

Intuition. Apply the same greedy to the answer rather than to each x. Suppose the top bits of the best possible XOR are already known, and call that partial answer answer. Can the next bit b also be 1? Let candidate = answer | (1 << b). It is achievable exactly when two numbers exist whose bits from 30 down to b XOR to candidate. Keep only those top bits of every number, x & mask, in a hash set. Now use the cancellation law: p ^ q = candidate holds exactly when q = p ^ candidate. So for each prefix p, look up p ^ candidate in the set. If any lookup succeeds, keep the 1; otherwise bit b of the answer is 0.

Algorithm.

1. answer = 0, mask = 0.
2. For b from 30 down to 0: add bit b to mask, collect {x & mask} into a set, form candidate, and keep it as the new answer if some prefix p has p ^ candidate in the set.
3. Return answer.

static int optimalPrefixSet(int[] nums) {
    int answer = 0, mask = 0;
    for (int b = HIGH_BIT; b >= 0; b--) {
        mask |= 1 << b;                                // keep bits HIGH_BIT..b of every number
        Set<Integer> prefixes = new HashSet<>();
        for (int x : nums) prefixes.add(x & mask);
        int candidate = answer | (1 << b);             // can bit b of the answer be 1 as well?
        for (int p : prefixes) {
            if (prefixes.contains(p ^ candidate)) {    // p ^ q == candidate  <=>  q == p ^ candidate
                answer = candidate;
                break;
            }
        }
    }
    return answer;
}

Complexity. Time O(31 · n) expected, because each round builds a set of n prefixes and does up to n lookups. Space O(n) for one round’s set.

Which to use. The prefix set uses less memory and only a few lines, but it answers just the single global question. The trie is the reusable tool: once built, it answers “best partner for this x” for any x, and it can be built incrementally. That is exactly what the next problem, where every query limits the allowed partners, needs.

Edge cases and pitfalls

• One element, or all elements equal. The answer is 0. Starting best at 0 handles it, and so does the trie, where x finds only itself.
• Large values. Integer.MAX_VALUE against 0 differs in all 31 bits and gives Integer.MAX_VALUE. The XOR of two non-negative ints never sets bit 31, so int is enough.
• Do not walk bit 31. 1 << 31 is negative. With non-negative inputs bit 31 never differs, so starting at bit 30 loses nothing.
• Negative numbers are out of scope. A partner with the opposite sign bit makes the XOR negative, so a greedy that prefers a 1 at bit 31 would pick the worst answer. Handle negatives separately if a variant allows them.
• Order of insertion. Inserting everything first and then querying is simplest. Inserting x after querying it also works, since pairing x with itself only gives 0.
• Memory. 2 × 10^5 numbers can create up to about 6 × 10^6 nodes. If that matters, preallocate a flat int[nodes][2] array instead of objects.

Related problems

• Bit PreRequisites for TRIE Problems explains the bit operations and the greedy argument used here.
• Maximum Xor with an element from an array adds an upper limit on the partner.
• Trie Implementation and Operations is the same structure over letters.
• Single Number - I is the classic use of x ^ x = 0.
• Count subarrays with given xor K uses the same p ^ q = c exactly when q = p ^ c lookup.