Maximum XOR of two numbers in an array

JavaView on GFG

Intuition

Find maximum XOR of any two elements. Trie of binary representations.

Algorithm

1Build trie of all numbers. For each number, greedily choose the opposite bit at each trie level.

Common Pitfalls

•Same as LC 421. Trie approach O(32n). Alternative: linear algebra over GF(2) for basis.

Maximum XOR of two numbers in an array.java

Java

// Approach: Trie of binary representations. For each number, traverse trie choosing opposite bit greedily.
// Time: O(n * 32) Space: O(n * 32)
class Solution {
    public int maxXor(int[] arr) {
        TrieNode root = new TrieNode();
        int maxResult = 0;

        for (int num : arr)
            insert(root, num);

        for (int num : arr)
            maxResult = Math.max(maxResult, findMaxXor(root, num));

        return maxResult;
    }

    private void insert(TrieNode root, int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null)
                node.children[bit] = new TrieNode();

            node = node.children[bit];
        }
    }

    private int findMaxXor(TrieNode root, int num) {
        TrieNode node = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = bit ^ 1;
            if (node.children[oppositeBit] != null) {
                maxXor |= (1 << i);
                node = node.children[oppositeBit];
            } else
                node = node.children[bit];

        }
        return maxXor;
    }
}

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

Was this solution helpful?