c++ beats 88.09% lg(n) with detailed and clear explain.


  • 0
    E

    Find a low:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (no.1-20)
    

    first:
    20 remained, eliminate odd numbers from the start, reserved numbers=even numbers/2

      1   2   3   4    5    6     7     8     9     10 (no.1-10)
    

    second:
    20/2=10 remained, 10 is even, so eliminate even numbers from the end, reserved numbers=(odd numbers+1)/2 (!!!can't be "odd numbers/2+1"!!!)

       1      2        3          4           5  (no.1-5)
    

    third:
    10/2=5 remained, eliminate odd numbers from the start, reserved numbers=even numbers/2

              1                   2 (no.1-2)
    

    forth:
    5/2=2 remained, 2 is even, so eliminate even numbers from the end, reserved numbers=(odd numbers+1)/2

              1
    

    There is only one remained,stop and begin to backtrack the result:

    ((1*2-1)*2*2-1)*2=6, and 6 is the solution.
    
    class Solution {
    public:
        int lastRemaining(int n) {
            return backtrack(n,1);
        }
        int backtrack(int n,bool is_from_head){
            if(n==1)return 1;
            if(is_from_head)return 2*backtrack(n/2,!is_from_head);
            else{
                if(n%2)return 2*backtrack(n/2,!is_from_head);
                else return 2*backtrack(n/2,!is_from_head)-1;
            }
        }
    };
    

Log in to reply
 

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