C++ O(nlogk) solution with ordering bits, with O(logk) additional memory for recursion stack


  • 1
    B

    The code below is a fixed version of my initial post thanks to @SergeyTachenov 's thorough analysis of the problem. In particular he indicated that the previous version fails for the following test cases:
    [4,6,7], [8,10,2], [14, 15, 9, 3, 2] and [15, 15, 9, 3, 2] which are currently not present in OJ and should be included.
    The current version, below works for all of these cases. Check out also @SergeyTachenov 's version here.

    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            if (nums.size() < 2) {
                return 0;
            } else if (nums.size() == 2) {
                return nums[0] ^ nums[1];
            }
            
            auto max = *max_element(nums.begin(), nums.end());
            auto msb = static_cast<int>(log2(max));
            auto msbSplit
                = partition(nums.begin(), nums.end(), [&](const int& n) { return (n & (1 << msb)) != 0; });
            
            while (msbSplit == nums.begin() || msbSplit == nums.end()) {
                --msb;
                if (msb == 0) {
                    return 0;
                }
                
                msbSplit
                    = partition(nums.begin(), nums.end(), [&](const int& n) { return (n & (1 << msb)) != 0; });
            }
    
            return findMaximumXor(nums.begin(), msbSplit, msbSplit, nums.end(), msb);
        }
        
        int findMaximumXor(const vector<int>::iterator& beginLeft,
                           const vector<int>::iterator& endLeft,
                           const vector<int>::iterator& beginRight,
                           const vector<int>::iterator& endRight,
                           int msb) {
            if (beginLeft == endLeft|| beginRight == endRight) {
                return 0;
            }
            
            if (msb == 0 || (distance(beginLeft, endLeft) == 1 && distance(beginRight, endRight) == 1)) {
                return *beginLeft ^ *beginRight;
            }
    
            auto mask = 1 << (msb - 1);
            auto splitLeft
                = partition(beginLeft, endLeft, [&](const int& n) { return (n & mask) != 0; });
            auto splitRight
                = partition(beginRight, endRight, [&](const int& n) { return (n & mask) != 0; });
                
            auto result1 = findMaximumXor(beginLeft, splitLeft, splitRight, endRight, msb - 1);
            auto result2 = findMaximumXor(splitLeft, endLeft, beginRight, splitRight, msb - 1);
                
            auto result = max(result1, result2);
            
            if (result == 0) {
                result = findMaximumXor(beginLeft, endLeft, beginRight, endRight, msb - 1);
            }
            
            return result;
        }
    };
    

  • 0

    @bartoszkp An interesting idea, but won't it degrade to O(n^2) in the worst case, just like quicksort does, if you have unlucky splits? And unlike quicksort, you can't randomize it to get good average case complexity.

    And it's not exactly without additional memory. In the best case it's O(lg N) recursion memory (it's not a tail recursion). In the worst case, if I'm right about degrading, it could use up to O(N) stack memory and even overflow.


  • 0
    B

    @SergeyTachenov Thank you for your feedback! I think it doesn't degrade in the same way as quicksort does - if in any split all elements fall into one bucket the recursion stops (due to:

    if (beginLeft == endLeft || beginRight == endRight) {
                return 0;
            }
    

    ). On the other hand thank you for pointing out that it's not a tail recursion! It's funny, because the whole idea for remaking my first successful submission was to make the solution tail recursive, but it took me a while and in the process I've forgot about my goal. Now looking at it, I'm not sure whether it's possible - I'll try!


  • 0

    OK, what if one bucket contains 3-5 elements, and the other one several thousand? Or something like that? And suppose the larger bucket is the left one, so recursion continues, and then there's another unlucky split just like that, and so on. So you'll get O(N) levels of recursion with a partition call in each. Surely, that's pretty unlikely, but we're talking about the worst case here, so the question is whether that's possible, not whether that's likely.


  • 1
    B

    @SergeyTachenov I think I see where the misunderstanding is. The number of levels of recursion will be always logk - it does not depend on the number of items in the buckets - only on the number of the highest most significant bit present. This is the relevant condition in the function:

          if (msb == 0) {
                return 0;
            }
    

  • 0

    @bartoszkp You're right! I felt like I was missing something, but I didn't think it was something that obvious!

    You can do a minor improvement here, by the way. Instead of finding the max element and fiddling around with log2, you could compute OR of all elements ANDed together with the complement of AND of all elements. This way you'll get the mask of all bits that you could possibly set to 1 in the result. That mask essentially says which bits are set in at least one element, but not in all of them. Then you can quickly skip bits set to zero in this mask because they are either all ones or all zeroes, and therefore will be set to zero in any XOR.


  • 0
    This post is deleted!

  • 1

    Actually, disregard that last (deleted) post with the code. I think this approach has a fatal flaw, at least as it's presented right now. I'll post a separate topic on that because I think it's really worth discussing.


  • 1

    OK, here it is. I think I was able to fix it, but those checks are ugly enough to allow a bug or two to slip in.


  • 0
    B

    @SergeyTachenov Thank you very much for your time and diligence! I need a few moments to analyse your approach and the flaws you've indicated.


  • 1
    B

    @SergeyTachenov I've followed your analysis and I am very grateful. I would have think that I've solved this problem but I wasn't careful enough. I've fixed the code above and also provided a link to your solution. Thanks again, cheers!


Log in to reply
 

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