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:
- Going left to right, delete the first number and then every other number after it.
- 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
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.
Hint 2
Every sweep halves the count and doubles the gap between neighbours.
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
- Start with
head = 1,step = 1,remaining = nand the direction left-to-right. - While
remaining > 1: if the sweep goes left to right, or the count is odd, the current head is deleted andhead += step. - Halve
remaining(rounding down), doublestep, and flip the direction. - 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 headJava
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