# Elimination Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/elimination-game)
Canonical: https://scaleengineer.com/dsa/problems/elimination-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Companies:** [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## Problem
\[Fetch error\]

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
*   Initialize a list (e.g., `ArrayList` in Java) with numbers from 1 to `n`.
*   Use a boolean flag, say `leftToRight`, initialized to `true`, 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 `leftToRight` is `true`, create a new list by taking every second element (at indices 1, 3, 5, ...) from the current list.
*   If `leftToRight` is `false`, 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 `leftToRight` flag.
*   Once the loop terminates, the list will contain a single element, which is the result.

## Recursive Approach with Recurrence Relation
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.
**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.
**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.
### Explanation
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.

```java
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));
    }
}
```
### Algorithm
*   Let `f(n)` be the function that returns the last remaining number for an initial list of `1...n`.
*   Derive a recurrence relation for `f(n)`. After the first left-to-right pass, the remaining numbers are `2, 4, 6, ...`, which is `2 * (1, 2, 3, ...)`.
*   The problem reduces to a subproblem on `n/2` elements, but starting with a right-to-left pass.
*   By relating the left-to-right game `f(n)` with the right-to-left game `g(n)`, we find `g(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.

## Iterative Approach with State Tracking
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.
**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`.
**Pros:** Optimal time complexity of O(log N).; Optimal space complexity of O(1).; Handles very large `N` without 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.
### Explanation
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 `head` becomes `old_head + old_step`.
- In a right-to-left pass, the first element is removed only if the number of elements is odd. So, if `remaining` is odd, `head` is updated similarly. Otherwise, it stays the same.
This logic can be combined and implemented in a simple loop.

```java
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;
    }
}
```
### Algorithm
*   Initialize state variables: `head = 1`, `step = 1`, `remaining = n`, and a boolean `fromLeft = true`.
*   Loop while `remaining > 1`.
*   Inside the loop, determine if the current `head` is eliminated. The `head` is 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 `head` is removed, update it: `head = head + step`.
*   Update the other state variables for the next pass: `remaining` is halved, `step` is doubled, and `fromLeft` is flipped.
*   When the loop terminates (`remaining == 1`), the `head` variable holds the final answer.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 a1

```