LeetCode 390 - Elimination Game

The problem gives us a sorted list containing every integer from 1 to n. We repeatedly eliminate numbers in alternating directions until only one number remains.

leetcodemediummathrecursion

LeetCode Problem 390

Difficulty: 🟡 Medium
Topics: Math, Recursion

Solution

Problem Understanding

The problem gives us a sorted list containing every integer from 1 to n. We repeatedly eliminate numbers in alternating directions until only one number remains.

The elimination process works like this:

  • In the first pass, we move from left to right and remove the first number and every other number after that.
  • In the second pass, we reverse direction and move from right to left, again removing the first encountered number and every other number.
  • We continue alternating directions until only one number remains.

The goal is to return that final remaining number.

For example, if n = 9, the sequence evolves like this:

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

The answer is 6.

The input consists of a single integer n, where 1 <= n <= 10^9. The upper bound is extremely important because it immediately tells us that explicitly constructing and modifying the array is not practical. Any algorithm that repeatedly removes elements from a list of size up to one billion would be far too slow and memory intensive.

The problem guarantees that n is always at least 1, so there is always at least one number in the list. This removes the need to handle empty input cases.

Several edge cases are important to think about early:

  • When n = 1, the answer is trivially 1.
  • Very large values such as 10^9 require an efficient mathematical solution.
  • Odd and even lengths behave differently during right-to-left elimination, which is one of the most common sources of bugs.
  • Repeated halving means we need to carefully track how the surviving sequence changes after each pass.

Approaches

Brute Force Approach

A straightforward simulation would explicitly build the list [1, 2, 3, ..., n] and repeatedly remove every other element while alternating directions.

For example:

  • Start with the full list.
  • Remove elements at alternating indices.
  • Reverse direction.
  • Repeat until only one element remains.

This approach is conceptually simple and directly follows the problem statement, so it is guaranteed to produce the correct answer.

However, it is far too slow for the constraints. Constructing a list of size 10^9 is already impossible within memory limits. Even for smaller inputs, repeatedly removing elements creates expensive operations because large portions of the list must be copied or shifted.

The brute-force solution therefore does not scale.

Optimal Mathematical Simulation

The key insight is that we do not need to store the actual list at all.

After each elimination round:

  • The remaining numbers form an arithmetic progression.
  • The spacing between surviving numbers doubles every round.
  • The count of remaining numbers halves every round.

Instead of tracking all surviving values, we only track:

  • The first remaining number, called head
  • The gap between remaining numbers, called step
  • The number of remaining elements
  • The current elimination direction

This works because the remaining sequence after each pass is always perfectly regular.

For example:

[2,4,6,8]

can be represented as:

  • head = 2
  • step = 2

After another elimination:

[2,6]

becomes:

  • head = 2
  • step = 4

By updating these variables mathematically, we can determine the final answer in logarithmic time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) to O(n²) O(n) Explicitly simulates removals from the list
Optimal O(log n) O(1) Tracks only the arithmetic progression state

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize four variables:
  • head = 1, the first remaining number
  • step = 1, the difference between consecutive surviving numbers
  • remaining = n, the number of elements still alive
  • left_to_right = True, the direction of elimination
  1. While more than one number remains, process one elimination round at a time.
  2. If we are eliminating from left to right, the first remaining number always changes.

For example:

[1,2,3,4,5,6] -> [2,4,6]

The new head becomes head + step. 4. If we are eliminating from right to left, the head changes only when the number of remaining elements is odd.

Consider:

[2,4,6,8]

Eliminating from the right gives:

[2,6]

The head stays 2.

But:

[2,4,6]

becomes:

[4]

Here the head changes because the count is odd. 5. Whenever the head should advance, update:

head += step
  1. After every elimination round:
  • Half the numbers remain:
remaining //= 2
  • The distance between surviving numbers doubles:
step *= 2
  • Reverse the direction:
left_to_right = not left_to_right
  1. Continue until only one number remains.
  2. Return head.

Why it works

The algorithm works because after every elimination round, the surviving numbers always form an arithmetic progression. Instead of storing every surviving number, we only need to know:

  • where the progression starts,
  • how far apart consecutive elements are,
  • how many elements remain.

The elimination rules determine exactly when the first element of the progression changes. Since each round halves the remaining numbers, the process completes in logarithmic time.

Python Solution

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

The implementation directly mirrors the mathematical simulation described earlier.

The variable head stores the first surviving number in the current sequence. The variable step stores the spacing between consecutive surviving numbers.

During each iteration of the loop, we determine whether the head should move forward. It always advances during left-to-right elimination because the first element is removed. During right-to-left elimination, it advances only when the remaining count is odd.

After processing a round, we halve the number of remaining elements because every other number is removed. We then double the step size because the surviving numbers become twice as far apart.

The direction flag alternates after every round until only one number remains.

Go Solution

func lastRemaining(n int) int {
    head := 1
    step := 1
    remaining := n
    leftToRight := true

    for remaining > 1 {
        if leftToRight || remaining%2 == 1 {
            head += step
        }

        remaining /= 2
        step *= 2
        leftToRight = !leftToRight
    }

    return head
}

The Go implementation follows the exact same logic as the Python version.

Since Go integers are fixed-width, it is worth considering overflow. However, the problem constraint of n <= 10^9 keeps all intermediate values safely within the range of Go's int type on modern platforms.

Unlike Python, Go requires explicit variable declarations and uses := for initialization. The boolean direction flag is toggled using !leftToRight.

Worked Examples

Example 1

Input:

n = 9

Initial sequence:

[1,2,3,4,5,6,7,8,9]
Round Direction Head Step Remaining Sequence
Start Left to Right 1 1 9 [1,2,3,4,5,6,7,8,9]
1 Left to Right 2 2 4 [2,4,6,8]
2 Right to Left 2 4 2 [2,6]
3 Left to Right 6 8 1 [6]

Final answer:

6

Example 2

Input:

n = 1
Round Direction Head Step Remaining Sequence
Start Left to Right 1 1 1 [1]

Since only one number exists initially, the answer is immediately:

1

Complexity Analysis

Measure Complexity Explanation
Time O(log n) The number of remaining elements halves every iteration
Space O(1) Only a fixed number of variables are used

The algorithm is highly efficient because each elimination round cuts the problem size in half. This produces logarithmic growth in the number of iterations. No additional arrays or data structures are created, so the memory usage remains constant.

Test Cases

solution = Solution()

assert solution.lastRemaining(1) == 1      # smallest possible input
assert solution.lastRemaining(2) == 2      # simple even case
assert solution.lastRemaining(3) == 2      # small odd case
assert solution.lastRemaining(4) == 2      # power of two
assert solution.lastRemaining(5) == 2      # odd length transition
assert solution.lastRemaining(6) == 4      # even length transition
assert solution.lastRemaining(7) == 4      # odd elimination behavior
assert solution.lastRemaining(8) == 6      # multiple elimination rounds
assert solution.lastRemaining(9) == 6      # provided example
assert solution.lastRemaining(10) == 8     # larger even case
assert solution.lastRemaining(24) == 14    # several alternating rounds
assert solution.lastRemaining(100) == 54   # medium-sized input
assert solution.lastRemaining(1000) == 510 # larger stress case
Test Why
n = 1 Validates smallest boundary value
n = 2 Tests simplest elimination
n = 3 Verifies odd-sized behavior
n = 4 Tests exact halving behavior
n = 5 Ensures odd-length right-to-left handling
n = 6 Tests even-sized transitions
n = 7 Verifies alternating direction correctness
n = 8 Tests multiple rounds on a power of two
n = 9 Validates provided example
n = 10 Confirms behavior on larger even input
n = 24 Tests several elimination cycles
n = 100 Medium-sized correctness check
n = 1000 Stress test for logarithmic behavior

Edge Cases

One important edge case is n = 1. A careless implementation might enter the elimination loop unnecessarily or incorrectly remove the only element. In this implementation, the loop condition is while remaining > 1, so the algorithm immediately returns 1 without performing any operations.

Another important edge case occurs during right-to-left elimination when the remaining count is odd. This is one of the trickiest parts of the problem. For example:

[2,4,6]

eliminated from right to left becomes:

[4]

The head changes because the first element is removed indirectly during the elimination pattern. The implementation correctly handles this with:

if left_to_right or remaining % 2 == 1:

A third important edge case involves extremely large values such as n = 10^9. Any implementation that explicitly stores the array would fail due to memory constraints. This solution avoids constructing the list entirely and instead tracks only four integer variables, allowing it to handle the maximum constraint efficiently.