C++ solution O(n) segregating by bits


  • 0
    J

    So I keep vector of pairs of vectors :
    for each pair of vectors
    for each number taken from the first vector
    for each number taken from the second vector
    xoring x most significant bits gives the best result

    Constant is brutal, but it's O(n) nonetheless.

    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            function<pair<vector<int>,vector<int>>(vector<int>&, int)> segregate = 
            [&](vector<int> &inp, int bit){
                vector<int> res1;
                vector<int> res2;
                for(int a: inp){
                    if(a & bit){
                        res2.push_back(a);
                    } else{
                        res1.push_back(a);
                    }
                }
                return make_pair(res1, res2);
            };
            if(nums.size() <= 1){
                return 0;
            }
            int bit;
            typedef vector<int> VI;
            vector<pair<VI,VI>> res;
            for(bit = 31; bit >= 0; bit--){
                pair<VI,VI> p = segregate(nums, 1 << bit);
                if(!p.first.empty() && !p.second.empty()){
                    res.push_back(p);
                    bit--;
                    break;
                }
            }
            if(res.empty()){
                return 0;
            }
            for(;bit >= 0; bit--){
                vector<pair<VI,VI>> res2;
                for(pair<VI,VI> & p: res){
                    pair<VI,VI> seg1 = segregate(p.first, 1 << bit);
                    pair<VI,VI> seg2 = segregate(p.second, 1 << bit);
                    for(int i = 0; i < 2; i++){
                        if(!seg1.first.empty() && !seg2.second.empty()){
                            res2.push_back({seg1.first, seg2.second});
                        }
                        swap(seg1, seg2);
                    }
                }
                if(!res2.empty()){
                    swap(res, res2);
                }
            }
            pair<VI,VI> last = res.back();
            return last.first[0]^last.second[0];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.