Trie and Bitwise Operations: Maximum XOR

Maximum XOR of Two Numbers in an Array (LeetCode 421)

Strategy: Represent each integer as its 32-bit binary sequence and insert it into a Binary Trie. During a search for x, greedily traverse the branch corresponding to the opposite bit of x at each level to maximize the XOR result.

class MaxXOR {
    // Array-based Trie for high performance
    private int[][] trie = new int[32 * 100005][2];
    private int nodesCount = 1;

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

    private int query(int x) {
        int node = 0, currentXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (x >> i) & 1;
            int desiredBit = 1 - bit; // Gready: try to take the opposite bit
            
            if (trie[node][desiredBit] != 0) {
                currentXor |= (1 << i); // Opposite bit exists, XOR bit is 1
                node = trie[node][desiredBit];
            } else {
                node = trie[node][bit]; // Must take the same bit, XOR bit is 0
            }
        }
        return currentXor;
    }

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

Complexity: $O(32N)$, a significant improvement over the $O(N^2)$ brute-force approach.

Maximum XOR with Query Constraints (LeetCode 1828 variant)

For problems requiring the maximum XOR under a limit or within a sliding window, a Persistent Trie or a Trie that supports Range Queries (using a count at each node) is often required.

// Logic for maximizing XOR against a fixed bit-mask
public int[] getMaximumXor(int[] nums, int maximumBit) {
    int n = nums.length;
    int mask = (1 << maximumBit) - 1; // All 1s mask for k bits
    int xorSum = 0;
    for (int x : nums) xorSum ^= x;
    
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        // xorSum ^ k = mask => k = xorSum ^ mask
        ans[i] = xorSum ^ mask;
        xorSum ^= nums[n - 1 - i]; // Simulate removing the last element
    }
    return ans;
}

Technical Summary: Binary Tries

Array Form vs. Object Form

// Array Form (Static Allocation)
// High performance, cache-friendly, used in competitive programming.
int[][] trie = new int[MAX_NODES][ALPHABET_SIZE];

// Object Form (Heap Allocation)
// Modular, easier to read, preferred in software engineering.
static class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

筋