Elimination Game

Medium
1276.

Elimination Game

Elimination Game is a medium coding problem on math and recursion, asked in Amazon and Bloomberg interviews.

Write the numbers 1, 2, …, n in a row, in increasing order. Then repeat these sweeps until a single number is left:

  1. Going left to right, delete the first number and then every other number after it.
  2. Going right to left, delete the rightmost number and then every other number before it.

The sweeps keep alternating direction. Return the number that survives.

Example 1

Input
n = 9
Output
6
Explanation
1 2 3 4 5 6 7 8 9 → 2 4 6 8 → 2 6 → 6.

Example 2

Input
n = 6
Output
4
Explanation
1 2 3 4 5 6 → 2 4 6 → 4.

Example 3

Input
n = 1
Output
1

Constraints

  • 1 <= n <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var lastRemaining = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Elimination Game — Solution in Python, Java & C++

Elimination Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and recursion.

Elimination Game is a medium coding problem on math and recursion, asked in Amazon and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Math, Recursion
  • Asked at: Amazon, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Write the numbers 1, 2, …, n in a row, in increasing order. Then repeat these sweeps until a single number is left:

  1. Going left to right, delete the first number and then every other number after it.
  2. Going right to left, delete the rightmost number and then every other number before it.

The sweeps keep alternating direction. Return the number that survives.

Example 1

Input: n = 9
Output: 6
Explanation: 1 2 3 4 5 6 7 8 9 → 2 4 6 8 → 2 6 → 6.

Example 2

Input: n = 6
Output: 4
Explanation: 1 2 3 4 5 6 → 2 4 6 → 4.

Example 3

Input: n = 1
Output: 1

Constraints

  • 1 <= n <= 10^9

Hints for Elimination Game

  1. Hint 1

    You cannot build the list for n = 10^9. Track only the first surviving number, the gap between survivors, and how many remain.

  2. Hint 2

    Every sweep halves the count and doubles the gap between neighbours.

  3. Hint 3

    The first survivor moves forward by one gap on a left-to-right sweep, and on a right-to-left sweep only when the count is odd.

How to solve Elimination Game

The survivors always form an arithmetic sequence, so it is enough to track its first term (head), its common difference (step) and its length.

Approach

  1. Start with head = 1, step = 1, remaining = n and the direction left-to-right.
  2. While remaining > 1: if the sweep goes left to right, or the count is odd, the current head is deleted and head += step.
  3. Halve remaining (rounding down), double step, and flip the direction.
  4. Return head.

Why it works

A left-to-right sweep always deletes the first element, so the new head is the old second element. A right-to-left sweep starts at the last element and deletes alternate ones; it reaches the first element exactly when the count is odd. Either way the survivors are every second element of the old sequence, so they remain an arithmetic sequence with double the difference and half the length (rounded down). After about log2 n sweeps one element is left, and it is the head.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • A right-to-left sweep removes the head only when the count is odd — with an even count the head survives.
  • Simulating the list is O(n) memory and far too slow for 10^9.
  • The step doubles each round; with n ≤ 10^9 it stays below 2^30, so 32-bit ints are fine.

Reference solution

Python

def lastRemaining(n: int) -> int:
    head, step, remaining, left = 1, 1, n, True
    while remaining > 1:
        if left or remaining % 2 == 1:
            head += step
        remaining //= 2
        step *= 2
        left = not left
    return head

Java

public static int lastRemaining(int n) {
    int head = 1, step = 1, remaining = n;
    boolean left = true;
    while (remaining > 1) {
        if (left || remaining % 2 == 1) head += step;
        remaining /= 2;
        step *= 2;
        left = !left;
    }
    return head;
}

C++

int lastRemaining(int n) {
    long long head = 1, step = 1, remaining = n;
    bool left = true;
    while (remaining > 1) {
        if (left || remaining % 2 == 1) head += step;
        remaining /= 2;
        step *= 2;
        left = !left;
    }
    return (int)head;
}

JavaScript

var lastRemaining = function(n) {
    var head = 1, step = 1, remaining = n, left = true;
    while (remaining > 1) {
        if (left || remaining % 2 === 1) head += step;
        remaining = Math.floor(remaining / 2);
        step *= 2;
        left = !left;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Recursion