Basically we calculate the next starting point, and we go forward and backwards each time.

Step gets multiplied by two at each loop iteration.

Complexity is θ(log N) because we divide n by 2 at each iteration. Size complexity is O(1).

```
class Solution(object):
def lastRemaining(self, n):
start, size, inv = 1, 1, 1
while n > 1: start, size, inv, n = start + inv * size + 2 * (n // 2 - 1) * inv * size,\
size * 2, inv * -1,\
n // 2
return start
```

Here's my 4-line O(n) O(n) code that didn't get accepted:

```
class Solution(object):
def lastRemaining(self, n):
def game(nums):
if len(nums) <= 1: return nums[0]
return game([nums[i] for i in range(1, len(nums), 2)][::-1])
return game([i for i in range(1, n + 1)])
```