Maximum XOR of Two Numbers in an Array

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

Example 1

Input: [3,10,5,25,2,8] → Output: 28 (5 XOR 25)

Example 2

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

Solution Approach

Use a Trie built on the 32-bit representation of each number. For each number, traverse the Trie trying to go the opposite bit direction (to maximize XOR). Build the Trie on all numbers first.

Build a binary Trie: for each number, insert all 32 bits (MSB first).
For each number, traverse the Trie greedily: prefer the branch whose bit differs from current bit.
XOR each chosen bit with the current bit and accumulate.
Return the maximum XOR found.

Java

class Solution {
    private int[][] trie = new int[32 * 10001][2];
    private int node = 1;

    public int findMaximumXOR(int[] nums) {
        for (int num : nums) insert(num);
        int max = 0;
        for (int num : nums) max = Math.max(max, query(num));
        return max;
    }

    private void insert(int num) {
        int cur = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (trie[cur][bit] == 0) trie[cur][bit] = node++;
            cur = trie[cur][bit];
        }
    }

    private int query(int num) {
        int cur = 0, xor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int want = 1 - bit;
            if (trie[cur][want] != 0) { xor |= (1 << i); cur = trie[cur][want]; }
            else cur = trie[cur][bit];
        }
        return xor;
    }
}

Time Complexity: O(N * 32)
Space Complexity: O(N * 32)