Elimination Game

Problem

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:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer n, return the last number that remains in arr.

Examples

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

Solution

Method 1 – Recursive Reduction

Intuition

The elimination process can be modeled recursively. At each round, the problem size halves, and the direction alternates. The key is to realize that after each pass, the remaining numbers form an arithmetic progression, and the problem can be reduced to a smaller instance.

Approach

1. If n == 1, return 1 (base case).
2. For each round, the first element is always removed, so the answer is always even.
3. Recursively solve for n // 2, then map the result back to the original sequence.
4. Use the formula: 2 * (1 + n//2 - eliminationGame(n//2)) for right-to-left, and 2 * eliminationGame(n//2) for left-to-right.
5. Alternate direction each round.

Code

C++

class Solution {
public:
    int lastRemaining(int n) {
        if (n == 1) return 1;
        return 2 * (1 + n/2 - lastRemaining(n/2));
    }
};

Go

func lastRemaining(n int) int {
    if n == 1 {
        return 1
    }
    return 2 * (1 + n/2 - lastRemaining(n/2))
}

Java

class Solution {
    public int lastRemaining(int n) {
        if (n == 1) return 1;
        return 2 * (1 + n/2 - lastRemaining(n/2));
    }
}

Kotlin

class Solution {
    fun lastRemaining(n: Int): Int {
        if (n == 1) return 1
        return 2 * (1 + n/2 - lastRemaining(n/2))
    }
}

Python

class Solution:
    def lastRemaining(self, n: int) -> int:
        if n == 1:
            return 1
        return 2 * (1 + n//2 - self.lastRemaining(n//2))

Rust

impl Solution {
    pub fn last_remaining(n: i32) -> i32 {
        if n == 1 {
            1
        } else {
            2 * (1 + n/2 - Solution::last_remaining(n/2))
        }
    }
}

TypeScript

class Solution {
    lastRemaining(n: number): number {
        if (n === 1) return 1;
        return 2 * (1 + Math.floor(n/2) - this.lastRemaining(Math.floor(n/2)));
    }
}

Complexity

• ⏰ Time complexity: O(log n), since the problem size halves each time.
• 🧺 Space complexity: O(log n), due to recursion stack.

Method 2 – Iterative Simulation

Intuition

Instead of recursion, we can simulate the process iteratively by tracking the head, step, and direction. This avoids recursion and is more space-efficient.

Approach

1. Initialize head = 1, step = 1, left = true, and remaining = n.
2. While remaining > 1:
   • If going left or remaining is odd, move head forward by step.
   • Halve remaining and double step.
   • Flip direction.
3. Return head.

Code

C++

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

Go

func lastRemaining(n int) int {
    head, step, left, remaining := 1, 1, true, n
    for remaining > 1 {
        if left || remaining%2 == 1 {
            head += step
        }
        remaining /= 2
        step *= 2
        left = !left
    }
    return head
}

Java

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

Kotlin

class Solution {
    fun lastRemaining(n: Int): Int {
        var head = 1
        var step = 1
        var left = true
        var remaining = n
        while (remaining > 1) {
            if (left || remaining % 2 == 1) head += step
            remaining /= 2
            step *= 2
            left = !left
        }
        return head
    }
}

Python

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

Rust

impl Solution {
    pub fn last_remaining(n: i32) -> i32 {
        let (mut head, mut step, mut left, mut remaining) = (1, 1, true, n);
        while remaining > 1 {
            if left || remaining % 2 == 1 {
                head += step;
            }
            remaining /= 2;
            step *= 2;
            left = !left;
        }
        head
    }
}

TypeScript

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

Complexity

• ⏰ Time complexity: O(log n), since the number of elements halves each round.
• 🧺 Space complexity: O(1), only a constant number of variables are used.