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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Elimination Game

Difficulty: Medium

Problem Description

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.

Key Insights

  • The elimination process alternates between removing elements from the left and right ends of the list.
  • The pattern of elimination can be observed, where after each round, the remaining numbers can be expressed in terms of sequences of even or odd indexed numbers.
  • The problem can be solved without simulating the entire elimination process, using mathematical observation of the patterns.

Space and Time Complexity

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

Solution

The solution employs a mathematical approach rather than a brute-force simulation. We utilize the observation that the numbers that remain after each round can be represented as a series of even-indexed or odd-indexed numbers based on the direction of elimination. The last remaining number can be derived mathematically by observing the pattern of eliminations, specifically focusing on the powers of 2 in relation to the size of the list.

Code Solutions

def lastRemaining(n: int) -> int:
    left_to_right = True  # Start from left to right
    remaining = n
    head = 1  # The first element in the current range
    
    while remaining > 1:
        if left_to_right:
            head += 1  # Remove the first element in left-to-right pass
        if remaining % 2 == 1:
            # If odd, the last element will be removed in right-to-left pass
            head += 1
        remaining //= 2  # Halve the remaining elements
        left_to_right = not left_to_right  # Switch direction
    
    return head
← Back to All Questions