Maximum XOR of Two Numbers in an Array Explained

Problem Statement

Given a non-empty array of integers nums, find the maximum value of nums[i] XOR nums[j] for any two indices i and j where i != j. This problem tests your ability to efficiently search for pairs that produce the largest XOR, often using a bit-by-bit construction approach or a trie to optimize comparisons.

Example

Input: nums = [3,10,5,25,2,8]

Output: 28

Explanation: The maximum XOR is achieved by 5 ^ 25 = 28.

Code

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set set = new HashSet<>();
            for (int num : nums) {
                set.add(num & mask);
            }
            int candidate = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(prefix ^ candidate)) {
                    max = candidate;
                    break;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(sol.findMaximumXOR(nums)); // 28
    }
}
            

def find_maximum_xor(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)
        prefixes = set(num & mask for num in nums)
        candidate = max_xor | (1 << i)
        for prefix in prefixes:
            if (prefix ^ candidate) in prefixes:
                max_xor = candidate
                break
    return max_xor

# Example usage
print(find_maximum_xor([3, 10, 5, 25, 2, 8]))  # 28
            

function findMaximumXOR(nums) {
    let max = 0, mask = 0;
    for (let i = 31; i >= 0; i--) {
        mask |= (1 << i);
        const prefixes = new Set(nums.map(num => num & mask));
        const candidate = max | (1 << i);
        for (let prefix of prefixes) {
            if (prefixes.has(prefix ^ candidate)) {
                max = candidate;
                break;
            }
        }
    }
    return max;
}

// Example usage
console.log(findMaximumXOR([3, 10, 5, 25, 2, 8])); // 28
            

Explanation

• Construct the maximum XOR bit by bit, starting from the most significant bit (31).
• Use a mask to extract prefixes of numbers up to the current bit.
• Store these prefixes in a set for efficient lookup.
• For each bit, try to set it to 1 in the candidate maximum and check if there exists a pair of prefixes whose XOR equals this candidate.
• If found, update max; otherwise, continue to the next bit.

Note