# LeetCode 390: Elimination Game

## Problem Restatement

We start with a sorted list of integers:

```python
[1, 2, 3, ..., n]
```

Then we repeatedly remove numbers until only one number remains.

The removal process alternates direction:

1. From left to right, remove the first number and every other number after it.
2. From right to left, remove the rightmost number and every other number before it.
3. Keep alternating directions.

Return the last remaining number.

For example, when `n = 9`:

```text
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 4, 6, 8]
[2, 6]
[6]
```

So the answer is `6`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Last remaining number |
| Constraint | `1 <= n <= 10^9` |

Example function shape:

```python
def lastRemaining(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 9
```

Start with:

```python
[1, 2, 3, 4, 5, 6, 7, 8, 9]
```

Remove from left to right:

```python
[2, 4, 6, 8]
```

Remove from right to left:

```python
[2, 6]
```

Remove from left to right:

```python
[6]
```

So the answer is:

```python
6
```

Example 2:

```python
n = 1
```

Only one number exists.

So the answer is:

```python
1
```

## First Thought: Simulate the List

The direct idea is to build the full list:

```python
arr = [1, 2, 3, ..., n]
```

Then repeatedly keep every other number.

For `n = 9`:

```python
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 4, 6, 8]
[2, 6]
[6]
```

This is easy to understand, but `n` can be as large as `10^9`.

We cannot build a list with one billion integers.

We need to track the pattern without storing the list.

## Key Insight

After each elimination round, the remaining numbers still form an arithmetic sequence.

For example:

```text
[1, 2, 3, 4, 5, 6, 7, 8, 9]
```

After removing from left to right:

```text
[2, 4, 6, 8]
```

This sequence has:

| Property | Value |
|---|---|
| First number | `2` |
| Step between numbers | `2` |
| Count | `4` |

After removing from right to left:

```text
[2, 6]
```

This sequence has:

| Property | Value |
|---|---|
| First number | `2` |
| Step between numbers | `4` |
| Count | `2` |

So we do not need the whole list.

We only track:

| Variable | Meaning |
|---|---|
| `head` | First remaining number |
| `step` | Distance between adjacent remaining numbers |
| `remaining` | Number of remaining values |
| `left_to_right` | Current removal direction |

The answer is `head` when only one number remains.

## When Does `head` Move?

The first remaining number changes in two cases.

Case 1: removing from left to right.

The first number is always removed, so `head` moves forward by `step`.

Case 2: removing from right to left with an odd number of elements.

Example:

```text
[2, 4, 6]
```

Remove from right:

```text
remove 6, then 2
```

The remaining list is:

```text
[4]
```

The head changes.

But with an even number of elements:

```text
[2, 4, 6, 8]
```

Remove from right:

```text
remove 8, then 4
```

The remaining list is:

```text
[2, 6]
```

The head stays the same.

So the rule is:

```python
if left_to_right or remaining % 2 == 1:
    head += step
```

After each round:

```python
remaining //= 2
step *= 2
left_to_right = not left_to_right
```

## Algorithm

Initialize:

```python
head = 1
step = 1
remaining = n
left_to_right = True
```

While more than one number remains:

1. If we remove from left to right, move `head`.
2. If we remove from right to left and `remaining` is odd, also move `head`.
3. Halve `remaining`.
4. Double `step`.
5. Flip direction.

Return `head`.

## Correctness

At the start of every round, the remaining numbers form an arithmetic sequence:

```text
head, head + step, head + 2 * step, ...
```

with `remaining` elements.

This is true initially, where `head = 1`, `step = 1`, and `remaining = n`.

During one elimination round, every other element is removed. The remaining elements therefore still form an arithmetic sequence, but the distance between adjacent remaining elements doubles. So `step *= 2` is correct.

The number of remaining elements is halved, so `remaining //= 2` is correct.

The only question is whether the first remaining value changes.

When removing from left to right, the first element is always removed, so the new first element is `head + step`.

When removing from right to left, the first element is removed only if the current count is odd. Therefore `head` moves by `step` exactly when `remaining` is odd.

Thus the update rule:

```python
if left_to_right or remaining % 2 == 1:
    head += step
```

keeps `head` equal to the first element of the remaining sequence after each round.

When only one element remains, the first element is also the last remaining element. Therefore returning `head` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each round halves the number of remaining elements |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
class Solution:
    def lastRemaining(self, n: int) -> int:
        head = 1
        step = 1
        remaining = n
        left_to_right = True

        while remaining > 1:
            if left_to_right or remaining % 2 == 1:
                head += step

            remaining //= 2
            step *= 2
            left_to_right = not left_to_right

        return head
```

## Code Explanation

We begin with the full sequence:

```python
head = 1
step = 1
remaining = n
left_to_right = True
```

The loop continues until one number remains:

```python
while remaining > 1:
```

Update the first remaining number when the current round removes it:

```python
if left_to_right or remaining % 2 == 1:
    head += step
```

Then update the sequence shape:

```python
remaining //= 2
step *= 2
```

Every round removes half the values, and the spacing between surviving values doubles.

Finally, alternate the direction:

```python
left_to_right = not left_to_right
```

When the loop ends, `head` is the only remaining number.

## Testing

```python
def test_solution():
    s = Solution()

    assert s.lastRemaining(1) == 1
    assert s.lastRemaining(2) == 2
    assert s.lastRemaining(3) == 2
    assert s.lastRemaining(4) == 2
    assert s.lastRemaining(5) == 2
    assert s.lastRemaining(6) == 4
    assert s.lastRemaining(7) == 4
    assert s.lastRemaining(8) == 6
    assert s.lastRemaining(9) == 6
    assert s.lastRemaining(10) == 8

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Minimum input |
| `n = 2` | One left-to-right elimination |
| `n = 3` | Odd count affects head |
| `n = 4` | Even count right-to-left keeps head |
| `n = 9` | Main example |
| `n = 10` | Checks behavior just after the main example |