Maximum XOR of Two Numbers in an Array

Medium
416.

Maximum XOR of Two Numbers in an Array

Maximum XOR of Two Numbers in an Array is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Microsoft interviews.

Given an integer array nums, return the maximum value of nums[i] XOR nums[j] over all pairs of indices 0 <= i <= j < n.

Example 1

Input
nums = [3,10,5,25,2,8]
Output
28
Explanation
5 XOR 25 = 28.

Example 2

Input
nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output
127

Example 3

Input
nums = [0]
Output
0

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 1000000000

Follow-up: The O(n²) scan is easy. Can you get O(32n) with a bit trie or a prefix hash set?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum XOR of Two Numbers in an Array — Problem & Solution

Maximum XOR of Two Numbers in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum XOR of Two Numbers in an Array is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given an integer array nums, return the maximum value of nums[i] XOR nums[j] over all pairs of indices 0 <= i <= j < n.

Example 1

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

Example 2

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Example 3

Input: nums = [0]
Output: 0

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 1000000000

Follow-up: The O(n²) scan is easy. Can you get O(32n) with a bit trie or a prefix hash set?

Hints for Maximum XOR of Two Numbers in an Array

  1. Hint 1

    Build the answer one bit at a time, from the most significant bit down.

  2. Hint 2

    Keep the prefixes of every number under a growing mask in a hash set.

  3. Hint 3

    If two prefixes p and q satisfy p ^ q == candidate, that bit is achievable — a set lookup for candidate ^ p decides it.

How to solve Maximum XOR of Two Numbers in an Array

Build the answer greedily bit by bit from the top: keep the prefixes under a growing mask in a set, and test whether some pair of prefixes XORs to the current candidate.

Approach

  1. For each bit from 31 down: extend the mask, collect x & mask for all x.
  2. Set candidate = best | (1 << bit); if any prefix p has candidate ^ p in the set, accept best = candidate.

Why it works

A higher bit is worth more than all lower bits combined, so committing to the best achievable prefix at each level is optimal; p ^ q == candidate is checked in O(1) via candidate ^ p ∈ set.

Complexity

  • Time — O(32 · n)
  • Space — O(n)

Pitfalls

  • A binary trie is the equivalent structural approach and handles streaming queries.

Reference solution

Python

def findMaximumXOR(nums) -> int:
    best = 0
    mask = 0
    for bit in range(31, -1, -1):
        mask |= 1 << bit
        prefixes = {x & mask for x in nums}
        candidate = best | (1 << bit)
        if any((candidate ^ p) in prefixes for p in prefixes):
            best = candidate
    return best

Java

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

C++

int findMaximumXOR(vector<int>& nums) {
    int best = 0, mask = 0;
    for (int bit = 30; bit >= 0; bit--) {
        mask |= 1 << bit;
        unordered_set<int> prefixes;
        for (int x : nums) prefixes.insert(x & mask);
        int candidate = best | (1 << bit);
        for (int p : prefixes) {
            if (prefixes.count(candidate ^ p) > 0) {
                best = candidate;
                break;
            }
        }
    }
    return best;
}

JavaScript

var findMaximumXOR = function(nums) {
    let best = 0;
    let mask = 0;
    for (let bit = 31; bit >= 0; bit--) {
        mask = mask | (1 << bit);
        const prefixes = new Set();
        for (let i = 0; i < nums.length; i++) prefixes.add((nums[i] & mask) >>> 0);
        const candidate = (best | (1 << bit)) >>> 0;
        let found = false;
        prefixes.forEach(function(p) {
            if (prefixes.has((candidate ^ p) >>> 0)) found = true;
        });
        if (found) best = candidate;
    }
    return best | 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets