LeetCode 390: Elimination Game

Problem Restatement

We start with a sorted list of integers:

[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:

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

So the answer is 6.

Input and Output

Example function shape:

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

Examples

Example 1:

n = 9

Start with:

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

Remove from left to right:

[2, 4, 6, 8]

Remove from right to left:

[2, 6]

Remove from left to right:

[6]

So the answer is:

6

Example 2:

n = 1

Only one number exists.

So the answer is:

1

First Thought: Simulate the List

The direct idea is to build the full list:

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

Then repeatedly keep every other number.

For n = 9:

[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:

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

After removing from left to right:

[2, 4, 6, 8]

This sequence has:

After removing from right to left:

[2, 6]

This sequence has:

So we do not need the whole list.

We only track:

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:

[2, 4, 6]

Remove from right:

remove 6, then 2

The remaining list is:

[4]

The head changes.

But with an even number of elements:

[2, 4, 6, 8]

Remove from right:

remove 8, then 4

The remaining list is:

[2, 6]

The head stays the same.

So the rule is:

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

After each round:

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

Algorithm

Initialize:

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:

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:

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

Implementation

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:

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

The loop continues until one number remains:

while remaining > 1:

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

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

Then update the sequence shape:

remaining //= 2
step *= 2

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

Finally, alternate the direction:

left_to_right = not left_to_right

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

Testing

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: