421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

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

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

// Bit Manipulation
int findMaximumXOR(vector<int>& nums) { // time: O(n); space: O(n)
    int max = 0, mask = 0; 
    unordered_set<int> st;
    for (int i = 31; i >= 0; --i) {
        mask |= (1 << i); // mask to help extract bits from left to right
        st.clear();
        for (int num : nums) {
            st.insert(num & mask); // get prefix bits of each number
        }
        int max_candidate = max | (1 << i); // desire to get the larger candidate in current iteration
        for (int prefix : st) {
            if (st.count(prefix ^ max_candidate)) { // a ^ b = c => a ^ c = b
                max = max_candidate;
                break;
            }
        }
    }
    return max;
}

// Trie (Prefix Tree)
struct TrieNode {
    int val;
    TrieNode *left, *right; // left: 1, right: 0
    TrieNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
int findMaximumXOR(vector<int>& nums) { // time: O(n); space: O(n)
    TrieNode* root = new TrieNode(0);
    // Build Trie
    TrieNode* cur = root;
    for (int num : nums) {
        for (int i = 31; i >= 0; --i) {
            int tmp = num & (1 << i);
            if (tmp == 0) {
                if (!cur->right) {
                    cur->right = new TrieNode(0);
                }
                cur = cur->right;
            } else {
                if (!cur->left) {
                    cur->left = new TrieNode(1);
                }
                cur = cur->left;
            }
        }
        cur = root; // reset
    }
    // Find xor max
    int res = 0;
    for (int num : nums) {
        int curMax = 0;
        for (int i = 31; i >= 0; --i) {
            int tmp = num & (1 << i);
            if (cur->left && cur->right) {
                if (tmp == 0) {
                    cur = cur->left;
                } else {
                    cur = cur->right;
                }
            } else {
                cur = cur->left ? cur->left : cur->right;
            }
            curMax += tmp ^ (cur->val << i);
        }
        cur = root; // reset
        res = max(res, curMax); // comparison b/w res & curMax
    }
    return res;
}