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;
}
}
};
```