Problem Description

The Elimination Game problem is as follows: Given an integer n, imagine a list of numbers from 1 to n in increasing order. You perform the following operation until only one number remains:

• Start from the left, remove the first number, and then every other number (i.e., remove all odd-indexed numbers).
• Then, reverse direction: start from the right, remove the first number (from the right), and then every other number.
• Continue alternating left-to-right and right-to-left eliminations until only one number remains.

Key constraints:

• There is only one valid solution for each input n.
• You cannot reuse eliminated elements.
• 1 <= n <= 10^9

Thought Process

At first glance, it may seem that we need to simulate the entire elimination process, removing elements from an array until one remains. However, with large values of n (up to 10⁹), this approach would be extremely inefficient and use too much memory.

The key insight is to recognize patterns in the elimination process. After each pass, half of the numbers are removed, and the remaining numbers form a new sequence with a different starting point and step size. By tracking how the head of the list, the step size, and the direction change after each elimination, we can avoid simulating the entire array and instead use a mathematical approach to find the answer efficiently.

Solution Approach

We can model the elimination process by maintaining four variables:

• head: the current first number in the sequence
• step: the gap between consecutive numbers in the current sequence
• remaining: how many numbers are left
• left: a boolean indicating the direction (left-to-right or right-to-left)

1. Initialize head = 1, step = 1, remaining = n, and left = True (start from the left).
2. While remaining > 1:
   • If eliminating from the left, or if eliminating from the right and remaining is odd, update head = head + step (because the first number is always eliminated in these cases).
   • Update step = step * 2 (since every other number is removed, the gap doubles).
   • Update remaining = remaining // 2 (half the numbers remain).
   • Toggle left (switch direction).
3. Return head as the last remaining number.

This approach avoids array simulation and works in logarithmic time.

Example Walkthrough

Let's walk through the process for n = 9:
Initial list: 1 2 3 4 5 6 7 8 9

1. Left to right: Remove 1, 3, 5, 7, 9 → Remaining: 2 4 6 8
2. Right to left: Remove 8, 6, 4 → Remaining: 2

• head = 1, step = 1, remaining = 9, left = True
• Left to right: head = 1 + 1 = 2, step = 2, remaining = 4, left = False
• Right to left: remaining is even, so head stays at 2, step = 4, remaining = 2, left = True
• Left to right: head = 2 + 4 = 6 (but since remaining = 2, only 2 and 6 left, so head = 6), step = 8, remaining = 1

Time and Space Complexity

• Brute-force approach: Simulating the elimination with an array would be O(n) time and O(n) space, which is infeasible for large n.
• Optimized approach: Our mathematical solution only iterates as many times as needed to halve n to 1, which is O(\log n) time and O(1) space. This is because after each elimination round, the number of remaining elements halves.

Summary

The Elimination Game problem is elegantly solved by recognizing the pattern in the elimination process and tracking only the head, step, and direction. This allows us to avoid simulating the entire list and instead use a mathematical approach that is both fast and memory-efficient, making it suitable even for very large values of n.

Code Implementation

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

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

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

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