Simple C++ O(n) solution using bitmask with explanations


  • 0
    M
    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            int ans = 0, sf = 0;
            for (int i = 30; i >= 0; --i) {
                int twoi = (1 << i);
                int cdd = ans | twoi;
                sf |= twoi;
                unordered_set<int> has;
                for (int x:nums) {
                    if (has.count(x&sf))
                        ans = cdd;
                    has.insert(cdd ^ (x&sf));
                }
            }
            
            return ans;
        }
    };
    

    The idea is to set the bits of the maximal XOR sum one by one starting with the most significant. When trying to set ith bit to 1, loop through the array to see if any two numbers whose XOR sum of the first i bits equals to the answer so far with the ith bit set to 1. If there are no such pair then the ith bit of the answer is 0.


Log in to reply
 

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