8 lines iterative O(logN) solution with explanation


  • 0
    F

    The idea is to keep track of the first and last element of the remaining list. Let's use left and right represent them respectively. Use step to track how many numbers we need to jump during scan. Initially, the left = 1, right = n and step = 2. after each scan step = step * 2

    For each left to right scan, the left will move forward by step/2. The right element will move toward left by step/2 depend on if (right- left) % step == 0. For each right to left scan, the right will move backward by step/2, and the left will move toward right by step/2 depends on if (right - left)%step == 0. So, we can easily come out following code, we use n represent right

        int lastRemaining(int n) {
            int left = 1, step = 2;
            bool lefttoright = true;
            while(left < n) {
                if (lefttoright)  {
                    if ((n-left)%step == 0) n -= step/2;
                    left += step/2;
                } else {
                    if ((n-left)%step == 0) left += step/2;
                    n -= step/2;
                }
                step <<= 1;
                lefttoright = !lefttoright;
            }
            return left;
        }
    

    We can optimize the code to remove direction check by change step = - (step * 2) and swap(left, right) after each scan. So, we get following code:

        int lastRemaining(int n) {
            int last = 1;
            for(int step = 2; last != n; step = -(step<<1)) {
                 if ((n-last)%step == 0)  n -= step/2;
                 last += step/2;
                 swap(last, n);
            }
            return last;
        }
    

Log in to reply
 

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