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. (link)

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<sup>5</sup>

• 0 <= nums[i] <= 2<sup>31</sup> - 1

Solution

• Convert each number in the array to its binary form and insert it into a trie.

• Each number can have up to 31 bits, so the trie can be 31 levels deep.

• Each node in the trie represents a bit, either 0 or 1.

• To find the maximum XOR, take each number and traverse the trie.

• While traversing, look for the opposite bit (if the current bit is 0, look for 1, and vice versa) to maximize the XOR value.

• If the opposite bit is found, move in that direction to get the maximum XOR.

• Continue this process for each number and keep track of the highest XOR value found.

Time - O(n)

class Node {
    Node[] nodeArr;

    Node(){
        nodeArr = new Node[2];
    }

    public void put(int bit, Node node){
        nodeArr[bit] = node;
    }

    public Node get(int bit){
        return nodeArr[bit];
    }

    public boolean containsKey(int bit){
        return nodeArr[bit] != null;
    }
}

class Trie {
    Node root;

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

    public void insert(int num){
        Node node = root;
        for(int i=31; i>=0; i--){
            int bit = (num>>i) & 1;
            if(!node.containsKey(bit)){
                node.put(bit, new Node());
            }
            node = node.get(bit);
        }
    }

    public int getMax(int x){
        int ans = 0;
        Node node = root;
        for(int i=31; i>=0; i--){

            int bit = (x>>i) & 1;
            int oppBit = 1-bit;

            if(node.containsKey(oppBit)){
                ans = ans | (1<<i);
                node = node.get(oppBit);
            }
            else{
                node = node.get(bit);
            }
        }
        return ans;
    }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        for(int i=0; i<nums.length; i++){
            trie.insert(nums[i]);
        }

        int ans = 0;

        for(int i=0; i<nums.length; i++){
            int currMax = trie.getMax(nums[i]);
            ans = Math.max(ans, currMax);
        }

        return ans;
    }
}