Maximum XOR of Two Numbers in an Array

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 2 * 10⁵
0 <= nums[i] <= 2³¹ - 1

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {
    // create binary trie and insert values by their binary representation
    const trie = new Trie();
    for (const n of nums) {
        trie.insert(n);
    }

    // find largest xor result starting with the MSB of each value
    let max = -Infinity; // overall max xor value
    for (const n of nums) {
        let curSum = 0; // max xor value using n
        let node = trie.root; // current node in trie

        // 32 bits
        for (let i = 31; i >= 0; i--) {
            let bit = (n >> i) & 1; // get ith bit
            if (node.children[bit ^ 1]) { // find [0, 1] that gives 1 after xor with bit
                curSum += (1 << i); // increase by 2 ** i
                node = node.children[bit ^ 1]
            } else { // no xor target to make 1 (ie. go with bit ^ bit = 0)
                node = node.children[bit];
            }
        }
        max = Math.max(max, curSum);
    }
    return max;
};

class Node {
    constructor() {
        this.children = [null, null]; // binary trie => two node values (0 and 1)
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    insert(value) {
        let r = this.root;
        for (let i = 31; i >= 0; i--) { // 32 bits
            let bit = (value >> i) & 1; // get ith bit
            if (!(r.children[bit])) {
                r.children[bit] = new Node();
            }
            r = r.children[bit];
        }
    }
}

We will use a binary trie to implement our solution. We first insert all values in nums into our trie trie by their binary representations. Next, we iterate through nums to find the max xor value by traversing trie. More specifically, we start from the MSB to the LSB for each n in nums; at every bit u of n, we attempt to find a bit v in node such that u ^ v = 1 => v = u ^ 1 (ie. u xor v maximizes our result, since 1 > 0). If such v does not exist in node, we are forced to go with u instead (ie. u ^ u = 0 which we want to avoid).

Problem​

Solution​

Problem

Solution