This problem is similar to Josephus problem when **k=2**, the recursive version is easy after referring to the josephus problem on wiki.

it is highly recommend to refer to Josephus problem first, because i am chinese, my english is poor, my explanation may not be good, but the wiki explanation is very good.

```
public int lastRemaining(int n) {
return ((Integer.highestOneBit(n) - 1) & (n | 0x55555555)) + 1;
}
```

recursive version

for example:

1,2,3,4,...n

if you start from the left to right, the result is **i**

then, if you start from right to left, the result is **n+1-i**

for n numbers, after one pass, there are n/2 left, each number is two times of the original,

1,2,3,4,5,6,7,8,9

after one pass

2,4,6,8

assume the result of 1,2,3,4 from left to right is f(4)

then the result of 1,2,3,4 from right to left is 5-f(4)

then the result of 2,4,6,8 from right to left is 2*(5-f(4))

this is the formula

* f(n)=2(1+n/2-f(n/2))** when n is 1, of course the result is 1

```
public int lastRemaining(int n) {
return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
}
```

non-recursive version:

```
public int lastRemaining(int n) {
Stack<Integer> stack = new Stack<>();
while (n > 1) {
n /= 2;
stack.push(n);
}
int result = 1;
while (!stack.isEmpty()) {
result = 2 * (1 + stack.pop() - result);
}
return result;
}
```