How do you solve Elimination Game on LeetCode?

Elimination Game (LeetCode #390) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: The elimination pattern can be observed to alternate between removing elements from both ends.

What is the brute force solution for Elimination Game?

The brute force approach for Elimination Game is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach simulates the entire elimination process directly. We repeatedly remove elements from the list until only one remains, following the specified left-to-right and right-to-left rules. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Elimination Game?

Elimination Game uses the following concepts: Math, Recursion. The recommended patterns to study are: Mathematical Patterns, Simulation.

What are the interview tips for Elimination Game?

Always start with a brute-force solution to clarify your understanding of the problem. Look for patterns in the problem that can simplify the solution. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Elimination Game?

Failing to recognize the alternating pattern and trying to simulate without a clear understanding. Not considering edge cases, such as when n is very small.

#390

Elimination Game

Medium

MathRecursionMathematical PatternsSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

The optimal solution leverages mathematical patterns observed in the elimination process, allowing us to compute the last remaining number without simulating the entire elimination.

⚙️

Algorithm

5 steps

1Step 1: Initialize two variables: start = 1 and step = 1.
2Step 2: While n > 1, check if the current round is left-to-right or right-to-left.
3Step 3: If left-to-right, increment start by step; otherwise, if n is odd, increment start by step.
4Step 4: Double the step size and halve n to reflect the remaining numbers.
5Step 5: Continue until only one number remains.

solution.py12 lines

1def lastRemaining(n):
2    start, step = 1, 1
3    left_to_right = True
4    while n > 1:
5        if left_to_right:
6            start += step
7        if n % 2 == 1:
8            start += step
9        n //= 2
10        step *= 2
11        left_to_right = not left_to_right
12    return start

ℹ

Complexity note: The time complexity is O(log n) because we halve n in each iteration, making the number of iterations logarithmic relative to n.

1The elimination pattern can be observed to alternate between removing elements from both ends.
2The last remaining number can be derived mathematically rather than through simulation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.