We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Elimination Game

Number: 390

Difficulty: Medium

Paid? No

Companies: Google, Autodesk, Bloomberg, Amazon

Problem Description

Given a sorted list of numbers from 1 to n, repeatedly remove elements in alternating rounds. First, remove the first element and every other element from left to right; then, remove the last element and every other element from right to left. Continue this process, alternating directions, until only one number remains. Return that number.

Key Insights

  • The head element (first element of the current list) always gets removed in the left-to-right elimination.
  • In right-to-left elimination, the head moves only when the count of remaining elements is odd.
  • Instead of simulating the removals (which would be inefficient for large n), update the head mathematically based on the current step and direction.
  • Use a loop that halves the number of remaining elements in each round, doubling the step size, and switching the elimination direction.

Space and Time Complexity

Time Complexity: O(log n) - The number of remaining elements is roughly halved each round. Space Complexity: O(1) - Only a constant amount of extra space is used.

Solution

Maintain variables for the head (starting at 1), step size (initially 1), remaining element count (n), and elimination direction (starting from left-to-right). In each round, update the head according to the following rules:

  • If eliminating from left-to-right, always update the head.
  • If eliminating from right-to-left, update the head only if the remaining number count is odd. After each round, double the step size and halve the remaining elements. Toggle the elimination direction. Continue until there is only one element remaining, which is the final answer.

Code Solutions

# Python solution for the Elimination Game problem

def lastRemaining(n: int) -> int:
    head = 1       # starting head of the list
    step = 1       # initial gap between numbers
    left_to_right = True  # initial elimination direction
    remaining = n  # total elements remaining

    # Continue until one element remains
    while remaining > 1:
        # When moving left to right, or when moving right to left with an odd number of elements,
        # update the head.
        if left_to_right or remaining % 2 == 1:
            head += step
        # Update the step size (elements are removed, doubling the gap)
        step *= 2
        # Halve the number of remaining elements
        remaining //= 2
        # Switch the direction for the next round
        left_to_right = not left_to_right
    return head

# Example usage:
# print(lastRemaining(9))  # Output: 6
← Back to All Questions