Watch 10 video solutions for Elimination Game, a medium level problem involving Math, Recursion. This walkthrough by CodingCat has 12,063 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
Given the integer n, return the last number that remains in arr.
Example 1:
Input: n = 9 Output: 6 Explanation: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 109Problem Overview: You start with numbers from 1 to n. In the first pass, remove every second number from left to right. In the next pass, remove every second number from right to left. Continue alternating directions until only one number remains. Return that final number.
Approach 1: Simulating the Elimination Process (O(n) time, O(n) space)
The most straightforward way is to simulate the list of numbers and repeatedly remove every second element. Start with an array [1..n], iterate through it, and keep only the numbers that survive each round. After each pass, reverse the direction of traversal to match the alternating rule. Each round roughly halves the list size, so the total work across all rounds is about n + n/2 + n/4 ..., which gives O(n) time and O(n) space for storing the list. This approach is useful for understanding the elimination pattern but wastes memory and does unnecessary copying.
Approach 2: Mathematical Simulation with Two Pointer Reduction (O(log n) time, O(1) space)
The key observation is that you never need the full list. You only need to track the first remaining number, the step size between surviving numbers, the remaining count, and the elimination direction. After each round, half of the numbers disappear, the step size doubles, and the direction flips. When eliminating from the left, the head always moves forward by step. When eliminating from the right, the head only moves if the remaining count is odd. This compact mathematical simulation reduces the problem to about log₂(n) rounds, giving O(log n) time with constant space. The reasoning relies on patterns in arithmetic progressions and alternating passes, which ties closely to math reasoning and can also be expressed recursively using recursion.
Recommended for interviews: The mathematical reduction approach is what interviewers expect. A quick brute-force simulation shows you understand the elimination process, but recognizing the arithmetic pattern and tracking the head, step, and direction demonstrates stronger algorithmic insight and reduces the complexity to O(log n) time and O(1) space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulating the Elimination Process | O(n) | O(n) | Good for understanding the elimination pattern or during initial brute-force reasoning. |
| Mathematical Simulation with Two Pointer Reduction | O(log n) | O(1) | Best for interviews and production solutions where minimal time and memory are required. |