## Algorithm

Problem Name: 390. Elimination Game

You have a list `arr` of all integers in the range `[1, n]` sorted in a strictly increasing order. Apply the following algorithm on `arr`:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer `n`, return the last number that remains in `arr`.

Example 1:

```Input: n = 9
Output: 6
Explanation:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
```

Example 2:

```Input: n = 1
Output: 1
```

Constraints:

• `1 <= n <= 109`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const lastRemaining = function(n) {
let left = true
let remaining = n
let step = 1
while (remaining > 1) {
if (left || remaining % 2 === 1) {
}
remaining = remaining >> 1
step = step * 2
left = !left
}
}
``````
Copy The Code &

Input

cmd
n = 9

Output

cmd
6

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def lastRemaining(self, n):
head, left, step, remaining = 1, 1, 1, n
while remaining > 1:
if left or remaining % 2: head += step
left = 1 - left
step *= 2
remaining //= 2
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
1