Maximum XOR of Two Numbers in an Array

Updated on 11 June, 2025
Maximum XOR of Two Numbers in an Array header image

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

  • Java
java
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;
    }
}

The provided Java solution focuses on determining the maximum XOR (exclusive OR) of two numbers from a given array. This challenge involves utilizing a trie (prefix tree) specifically designed to handle binary representations of integers.

  • Initially, determine the highest number in the array. This value dictates the maximum length in binary form which in turn sets the number of trie levels.
  • Construct a binary trie where each node potentially has two children: one for a binary 0 and the other for a binary 1.
  • Traverse each number in the array, and for each bit in its binary representation:
    • Insert the current bit into the trie if it's not already present.
    • Simultaneously, attempt to traverse down the path that represents the opposite bit (bit XOR 1) to maximize the current path's XOR value.
  • If the opposite path exists, follow it to ensure the XOR value is maximized for this bit; otherwise, continue on the current path.
  • Keep track of and update the best XOR value encountered.

Utilizing a trie in this way leverages its structure to efficiently compare and contrast bits of the numbers, allowing the algorithm to compute the maximal XOR by only comparing each number once against the constructed trie. As a result, this approach likely offers a significant performance improvement over a naive double loop comparison, especially in cases with large arrays or large numbers.

Comments

No comments yet.