Annotated C++ solution with bit shifts


  • 0
    K
    int findMaximumXOR(vector<int>& nums) {
        // Let's first create a look up for patterns of most significant
        //  bits (MSB) for each of the 32 possible bit shifts
        set<int> lookUp[32];
        for(int shift=0; shift<32; shift++)
            for(auto a : nums)
                lookUp[shift].insert(a>>shift); // just acknowledge any existing
    
        // Remembering that _a_ xor _b_ = _c_ <=> _a_ xor _c_ = _b_ turns
        //  our search for _b_ achieving the largest _c_ into a construction
        //  of largest _c_ guided by the requirement that corresponding _b_
        //  exists in _nums_.
        // Here our _lookUp_ comes handy as it allows us to home in to the
        //  largest _c_ in a single run over its bits.
        //  To do so we maintain the _cMSB_ - a set of most significant bits
        //  of _c_ that, xor'ed with _a_, match any pattern in _lookUp_
        //  (i.e. match MSB of some _b_). Extending _cMSB_ to include next
        //  bit is simply a single left-bit-shift followed by an optimistic
        //  attempt to search a wider pattern with LSB set to 1 (to maximize
        //  _c_) that, if fails, means that we need to leave it set to 0. 
        int retval = 0;
        for(auto a : nums){
            int cMSB = 0;
            for(int shift=31; shift>=0; shift--){
                cMSB <<= 1;
                auto match = lookUp[shift].find( (a>>shift)^(cMSB|0x1) );
                if( match != lookUp[shift].end() )
                    cMSB |= 1;
            }
            if( retval < cMSB ) retval = cMSB;
        }
        return retval;
    }

Log in to reply
 

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