Elimination Game
MedPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the elimination process as described in the problem. We use a dynamic list of numbers, and in each step, we iterate through the list to remove elements according to the rules, alternating the direction of removal until only one number is left.
Algorithm
- Initialize a list (e.g.,
ArrayListin Java) with numbers from 1 ton. - Use a boolean flag, say
leftToRight, initialized totrue, to track the direction of elimination. - Start a loop that continues as long as the size of the list is greater than 1.
- Inside the loop, if
leftToRightistrue, create a new list by taking every second element (at indices 1, 3, 5, ...) from the current list. - If
leftToRightisfalse, create a new list by taking every second element starting from the end of the current list. - Replace the current list with the newly created list.
- Flip the
leftToRightflag. - Once the loop terminates, the list will contain a single element, which is the result.
Walkthrough
The most straightforward way to solve the problem is to perform the simulation step-by-step. We can maintain a list of the numbers that are currently in the game. In each round, we create a new list containing only the numbers that survive the elimination. For a left-to-right pass, we keep the elements at odd-numbered positions (2nd, 4th, 6th, etc.). For a right-to-left pass, we do the same but starting from the end. We repeat this process, alternating directions, until our list contains only one number.
import java.util.ArrayList;import java.util.List; class Solution { public int lastRemaining(int n) { if (n == 1) { return 1; } List<Integer> numbers = new ArrayList<>(); for (int i = 1; i <= n; i++) { numbers.add(i); } boolean leftToRight = true; while (numbers.size() > 1) { List<Integer> nextNumbers = new ArrayList<>(); if (leftToRight) { for (int i = 1; i < numbers.size(); i += 2) { nextNumbers.add(numbers.get(i)); } } else { // rightToLeft for (int i = numbers.size() - 2; i >= 0; i -= 2) { // Add to the front to maintain order nextNumbers.add(0, numbers.get(i)); } } numbers = nextNumbers; leftToRight = !leftToRight; } return numbers.get(0); }}Complexity
Time
O(N). The total number of operations across all passes is proportional to N + N/2 + N/4 + ... + 1, which is a geometric series that sums to O(N).
Space
O(N). We need to store the list of numbers, which initially has `N` elements. In each step, we create a new list of about half the size.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem description.
Cons
Highly inefficient for large values of
n.Prone to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors on competitive programming platforms.
This approach avoids simulating the list and instead finds a mathematical recurrence relation for the solution. By observing the pattern of how the remaining numbers change, we can define the solution for n in terms of the solution for n/2. This leads to a much faster logarithmic time complexity.
Algorithm
- Let
f(n)be the function that returns the last remaining number for an initial list of1...n. - Derive a recurrence relation for
f(n). After the first left-to-right pass, the remaining numbers are2, 4, 6, ..., which is2 * (1, 2, 3, ...). - The problem reduces to a subproblem on
n/2elements, but starting with a right-to-left pass. - By relating the left-to-right game
f(n)with the right-to-left gameg(n), we findg(n) = n + 1 - f(n). - This leads to the recurrence relation:
f(n) = 2 * (n/2 + 1 - f(n/2)). - The base case is
f(1) = 1. - Implement this relation using a recursive function.
Walkthrough
We can analyze the problem from a mathematical perspective. Let f(n) be the result for n elements. After the first pass (left-to-right), we are left with n/2 numbers: 2, 4, 6, .... This is equivalent to twice the list 1, 2, 3, .... The next pass on this new list is from right-to-left. Let's define g(m) as the result of a game on 1...m that starts with a right-to-left pass. We can establish a relationship between the standard game f(m) and g(m) by observing the symmetry: f(m) + g(m) = m + 1. Combining these observations, we arrive at the recurrence relation f(n) = 2 * (n/2 + 1 - f(n/2)). With the base case f(1) = 1, we can solve this recursively.
class Solution { public int lastRemaining(int n) { // Base case for the recursion if (n == 1) { return 1; } // Applying the recurrence relation: f(n) = 2 * (n/2 + 1 - f(n/2)) return 2 * (n / 2 + 1 - lastRemaining(n / 2)); }}Complexity
Time
O(log N). The input `n` is halved in each recursive call, leading to a logarithmic number of calls.
Space
O(log N). This is due to the recursion stack depth, which is proportional to the number of recursive calls until `n` becomes 1.
Trade-offs
Pros
Very efficient with O(log N) time complexity.
The code is elegant and concise.
Cons
Uses O(log N) space for the recursion stack, which is less optimal than an iterative solution.
For extremely large N (beyond typical integer limits), it could lead to a StackOverflowError.
This is the most optimal approach, achieving logarithmic time complexity with constant space. Instead of creating the list or using recursion, we track the state of the game through several variables: the first number of the remaining list (head), the gap between consecutive numbers (step), the count of remaining numbers (remaining), and the direction of elimination. We update these variables in a loop until only one number remains.
Algorithm
- Initialize state variables:
head = 1,step = 1,remaining = n, and a booleanfromLeft = true. - Loop while
remaining > 1. - Inside the loop, determine if the current
headis eliminated. Theheadis removed if the pass is from the left, OR if the pass is from the right and there's an odd number of elements. - If the
headis removed, update it:head = head + step. - Update the other state variables for the next pass:
remainingis halved,stepis doubled, andfromLeftis flipped. - When the loop terminates (
remaining == 1), theheadvariable holds the final answer.
Walkthrough
This approach is an iterative optimization of the recursive logic. We notice that at any point, the remaining numbers form an arithmetic progression. We can fully describe this progression by its first element (head), the common difference (step), and the number of elements (remaining). We can then simulate the game by updating these three variables in a loop.
Initially, head = 1, step = 1, and remaining = n. In each pass, remaining is halved and step is doubled. The main logic is to figure out how head changes.
- In a left-to-right pass, the first element is always removed, so the new
headbecomesold_head + old_step. - In a right-to-left pass, the first element is removed only if the number of elements is odd. So, if
remainingis odd,headis updated similarly. Otherwise, it stays the same. This logic can be combined and implemented in a simple loop.
class Solution { public int lastRemaining(int n) { int head = 1; int step = 1; int remaining = n; boolean fromLeft = true; while (remaining > 1) { // The head is updated if we move from the left, or if we move from the right // with an odd number of elements remaining. if (fromLeft || remaining % 2 == 1) { head = head + step; } // Update state for the next pass remaining = remaining / 2; step = step * 2; fromLeft = !fromLeft; } return head; }}Complexity
Time
O(log N). The loop runs as long as `remaining > 1`, and `remaining` is halved in each iteration.
Space
O(1). We only use a few variables to store the state, regardless of the size of `n`.
Trade-offs
Pros
Optimal time complexity of O(log N).
Optimal space complexity of O(1).
Handles very large
Nwithout any issues like stack overflow or memory limits.
Cons
The logic for updating the head can be less intuitive to derive compared to direct simulation.
Solutions
Solution
class Solution {public int lastRemaining(int n) { int a1 = 1, an = n, step = 1; for (int i = 0, cnt = n; cnt > 1; cnt >>= 1, step <<= 1, ++i) { if (i % 2 == 1) { an -= step; if (cnt % 2 == 1) { a1 += step; } } else { a1 += step; if (cnt % 2 == 1) { an -= step; } } } return a1; }}class Solution {public: int lastRemaining(int n) { int a1 = 1, an = n, step = 1; for (int i = 0, cnt = n; cnt > 1; cnt >>= 1, step <<= 1, ++i) { if (i % 2) { an -= step; if (cnt % 2) a1 += step; } else { a1 += step; if (cnt % 2) an -= step; } } return a1; }};class Solution: def lastRemaining(self, n: int) -> int: a1, an = 1, n i, step, cnt = 0, 1, n while cnt > 1: if i % 2: an -= step if cnt % 2: a1 += step else: a1 += step if cnt % 2: an -= step cnt >>= 1 step <<= 1 i += 1 return a1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.