Leetcode 421: Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/

Notes:

This O(n) solution to this question is not that straightforward. There is one implicit condition: there are only 32 digits for each number in the binary form. So we can check them digit by digit. But how can we do this?

One solution is found here:



The basic idea is to scan all the number from most significant bit to the least one by using bit mask. For each step, we exam essentially 1 bit more, then gradually cover all of them.

See the code below:

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0,mask = 0;
        for(int i=31; i>=0; --i){
            mask = mask | (1<<i);
            set<int> s;
            for(auto &n : nums) {
                s.insert(mask & n);
            }
            int nextTry = res | (1<<i);//exam whether the the ith bit is 1 or 0.
            for(auto &j : s){
                if(s.count(nextTry ^ j)){// is 1
                    res = nextTry;
                    break;
                }
            }
        }
        return res;
    }
};

There is another way implementing with a binary search tree (or trie). See the code below:

class Solution {
public:
    class TreeNode {
    public:
        TreeNode* next[2];
     //   TreeNode(): next[0](NULL), next[1](NULL) {}//constructor;
        TreeNode() {next[0] = NULL; next[1] = NULL;};//constructor;
        ~TreeNode() {//destructor;
            for(auto &a : next) delete a;
        }
    };

    int findMaximumXOR(vector<int>& nums) {
        int res = 0;
        TreeNode *root = buildTree(nums);
        for(auto &a : nums) {
            res = max(res, helper(root, a));
        }
        return res;
    }

    TreeNode* buildTree(vector<int> &vs) {//build a tree, return the root;
        TreeNode *root = new TreeNode(), *cur;
        for(auto &a : vs) {
            cur = root;
            for(int i=31; i>=0; --i) {
                int index = (a >> i) & 1;
                if(!cur->next[index]) cur->next[index] = new TreeNode();
                cur = cur->next[index];
            }
        }
        return root;
    }
   
    int helper(TreeNode* cur, int num) {
        int res = 0;
        for(int i=31; i>=0; --i) {
            int index = ((num >> i) & 1) ? 0 : 1;//XOR
            res <<= 1;
            if(cur->next[index]) {
                res |= 1;
                cur = cur->next[index];
            }
            else {
                res |= 0;
                cur = cur->next[index?0:1];
            }
        }
        return res;
    }
};