Maximum XOR of Two Numbers in an Array

Problem Statement

In this problem, we are provided with an integer array nums. The goal is to determine the maximum XOR value from any two elements ( nums[i] ) and ( nums[j] ) in the array, where the position indices satisfy ( 0 \leq i \leq j < n ), with ( n ) being the length of the array. The XOR (exclusive OR) operation returns a value where the bits are set to 1 if and only if exactly one of the corresponding bits of the operands is 1.

Examples

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 * 105
• 0 <= nums[i] <= 231 - 1

Approach and Intuition

The solution for the maximum XOR value can be understood and broken down as follows:

1. Understanding XOR:

   • The XOR operation results in 1 only when the bits differ. For instance, 5 (0101 in binary) XOR 3 (0011 in binary) results in 6 (0110 in binary).

2. Initial Thoughts:

   • A naive approach would involve computing the XOR for every possible pair ( (i, j) ) where ( 0 \leq i \leq j ). But given the constraints where ( n ) can be very large, this method becomes computationally expensive as it would have a time complexity of ( O(n^2) ).

3. Optimized Strategy Using Tries:

   • Consider using a trie (prefix tree) to store the binary representations of the numbers to efficiently search the potential pairs that could yield the maximum XOR value. This approach exploits the property that the XOR of two numbers is maximized when their binary representations differ the most.

4. Example Clarification:

   • Example 1: Value 5 (binary: 0101) and value 25 (binary: 11001) can be combined (using bits where they differ maximally) to achieve 28 (binary: 11100). Walking through such a prefix tree can point to the optimal pair.
   • Example 2: The process is similar, where the trie would help in finding the two numbers in the array which, when XORed, give the maximum result of 127.

By leveraging an algorithm designed to optimally search for two numbers whose bits maximize the XOR outcome and utilizing a trie data structure tailored for binary operations, we can significantly cut down computation time while adhering to the provided constraints. This approach directly tackles the challenge imposed by large num arrays within permissible computational limits.

Solutions

class BinaryTrieNode {
    BinaryTrieNode[] links = new BinaryTrieNode[2];
}
    
class Finder {
    public int findMaxXOR(int[] values) {
        int highestValue = values[0];
        for (int value : values) {
            highestValue = Math.max(highestValue, value);
        }
            
        int maxLength = Integer.toBinaryString(highestValue).length();
        int bestXor = 0;
    
        BinaryTrieNode rootHead = new BinaryTrieNode();
        for (int num : values) {
            BinaryTrieNode node = rootHead, xorNode = rootHead;
            int thisXor = 0;
                
            for (int j = maxLength - 1; j >= 0; j--) {
                int bit = (num >> j) & 1;
                int oppositeBit = bit ^ 1;
                    
                if (node.links[bit] == null) {
                    node.links[bit] = new BinaryTrieNode();
                }
                node = node.links[bit];
                    
                if (xorNode.links[oppositeBit] != null) {
                    thisXor |= (1 << j);
                    xorNode = xorNode.links[oppositeBit];
                } else {
                    xorNode = xorNode.links[bit];
                }
            }
            bestXor = Math.max(bestXor, thisXor);
        }
            
        return bestXor;
    }
}