C++ only bit operations O(logN) solution with explanation


  • 0
    T

    We can use 4 variables to represent the current array.

    last: the last digit of the array
    len: current length of the array
    gap: the gap between each digit
    i: even/odd counter
    

    In each iteration, we have the following transition:

    1. len = len/2;
    2. gap = gap*2;
    3. i = 1 - i;
    4. last = last - gap if (len == odd) or (i == 1) [elimination from right]
      last = last otherwise
    int lastRemaining(int n) {
            int last = n, len = n, gap = 1;
            bool i = 0;
            while (len > 1){
                if (len & 1 == 1 || i == 1){
                    last -= gap;
                }
                i = !i;
                len = len >> 1;
                gap = gap << 1;
            }
            return last;
        }
    

    Hope you find it helpful.


  • 0
    Q

    @tonygogogo logically, shouldn't
    if (len & 1 == 1 | i == 1) be (if (len & 1 == 1 || i == 1) ? a typo?


  • 0
    T

    Hi @quesder yes it should be a "||" , although "|" also gives the right answer. I have updated my answer, thanks!


Log in to reply
 

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