Short C++ solution based on splitting sets


  • 0
    R

    Inspired by @sandeep36.

    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            return maxXOR(nums, nums, 31);
        }
    
        int maxXOR(vector<int> a, vector<int> b, int n) {
            if (a.empty() || b.empty()) return 0;
            int mask = 1;
            for (int i = 0; i < n; i++) mask <<= 1;
            vector<int> a0, a1, b0, b1; // a0: subset from a with nth bit 0
            for (auto x : a)
                if ((x & mask) == 0) a0.push_back(x);
                else a1.push_back(x);
            for (auto x : b)
                if ((x & mask) == 0) b0.push_back(x);
                else b1.push_back(x);
            if (n == 0) return (!a0.empty() && !b1.empty()) || (!a1.empty() && !b0.empty());
            if ((!a0.empty() && !b1.empty()) || (!a1.empty() && !b0.empty())) // nth bit has 0, 1
                return mask + max(maxXOR(a0, b1, n-1), maxXOR(a1, b0, n-1));
            else // nth bit all 0, or all 1, thus ignored
                return maxXOR(a, b, n-1);
        }
    };

Log in to reply
 

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