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

• 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);
}