Elimination Game

medium math simulation

Problem

Numbers 1..n in order. Repeatedly remove every other starting from the first; then from the last to the first; alternate until only one remains. Return that number.

Inputn = 9

Output6

After two passes: [2,4,6,8]; right-to-left strip leaves [2,6]; final left-to-right pass leaves [6].

def last_remaining(n):
    head = 1
    step = 1
    left = True
    while n > 1:
        if left or n % 2 == 1:
            head += step
        n //= 2
        step *= 2
        left = not left
    return head

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

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

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

Explanation

Instead of actually building and trimming the list (which would be slow), we only track the first surviving number, called head. Every pass we update head, halve the count, and double the gap between survivors.

We keep three things: head (the current smallest survivor), step (the spacing between survivors, which doubles each pass), and left (whether this pass goes left-to-right).

The rule for when head moves: on a left-to-right pass the head is always removed, so head += step. On a right-to-left pass the head only gets removed when the remaining count n is odd (n % 2 == 1). After each pass we do n //= 2, step *= 2, and flip left.

When only one number is left (n == 1), head is the answer.

Example: n = 9. Pass 1 (left→right) moves head to 2, step 2, n=4. Pass 2 (right→left, n even) keeps head at 2, step 4, n=2. Pass 3 (left→right) moves head to 6, n=1. Answer is 6.

Time: O(log n) Space: O(1)