Naive o(lgn) method with comments. Easy to understand


  • 0
    X
    class Solution {
    public:
        int lastRemaining(int n) {
            int i=1,step=1;
            bool add=true;
            while((i+step>=1&&i+step<=n)||(i-step>=1&&i-step<=n)){//the last remaining number must be the one that either increasing or decreasing with the step will go beyond the boundary [1,n]
                step*=2;
                if(add){
                    i=n-(n-i)%step;// calculate the last eleminated number
                    if(i+step/2<=n) i+=step/2;// find the starting number of the next round
                    else if(i-step/2<=n) i-=step/2;
                    add=false; //alternate the direction 
                }else{
                    i=i%step; //calculate the last eleminated number
                    if(i-step/2>=1) i-=step/2;// find the starting number of the next round
                    else if(i+step/2>=1) i+=step/2;
                    add=true; //alternate the direction 
                }
            }
            return i;
        }
    };

Log in to reply
 

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