My simple O(log n) solution in C++:D&C


  • 0
    K

    class Solution {
    public:
    int lastRemaining(int n) {
    if(n==1)return 1;
    if(n%2)n--;
    int p=1,q,d=1,r=1,ans;
    q=r+(p*(n-1)d);
    while(n>1)
    {
    p
    =-1;d*=2;n/=2;r=q;
    if(n%2)q=r+(p*(n-2)d);
    else q=r+(p
    (n-1)*d);
    }
    return r;
    }
    };


  • 0
    C

    class Solution {
    public:
        int f(int n,bool d){
            if(1 == n)return 1;
            return (f(n>>1,1-d)<<1)-(!(0x1&n)&&d);
        }
        int lastRemaining(int n) {
            return f(n,0);
        }
    };
    

Log in to reply
 

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