390. Elimination Game

Description

The problem involves repeatedly eliminating numbers from a list of integers from 1 to n by alternating directions (left to right, then right to left) and removing every second number until only one number remains. The task is to determine the last remaining number.

Intuition

The key observation is that the first number (head) changes whenever we eliminate numbers from left to right or when the number of remaining elements is odd during right-to-left elimination. The step size also doubles after every elimination.

Approach

1. Initialize variables: - left to indicate the direction of elimination (starting from the left). - remaining for the count of remaining numbers. - step to track the current step size. - head to track the first remaining number in the current sequence.
2. In each iteration of the while loop: - If eliminating from the left or the number of remaining elements is odd, increment the head by step. - Divide remaining by 2 as half of the numbers are eliminated. - Double the step size. - Toggle the direction (left).
3. Repeat until only one number remains, which is stored in head.

Complexity

Time Complexity:

O(log n) since we halve the number of elements in each step.

Space Complexity:

O(1) as we use constant extra space.

Code

C++

class Solution {
public:
    int lastRemaining(int n) {
        bool left = true;
        int remaining = n;
        int step = 1;
        int head = 1;

        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:
        left = True
        remaining = n
        step = 1
        head = 1

        while remaining > 1:
            if left or remaining % 2 == 1:
                head += step
            remaining //= 2
            step *= 2
            left = not left

        return head

Java

class Solution {
    public int lastRemaining(int n) {
        boolean left = true;
        int remaining = n;
        int step = 1;
        int head = 1;

        while (remaining > 1) {
            if (left || remaining % 2 == 1) {
                head += step;
            }
            remaining /= 2;
            step *= 2;
            left = !left;
        }

        return head;
    }
}

JavaScript

var lastRemaining = function (n) {
    let left = true;
    let remaining = n;
    let step = 1;
    let head = 1;

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