{x}
blog image

Elimination Game

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.

 

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

 

Constraints:

  • 1 <= n <= 109

Solution Explanation for Elimination Game

This problem involves repeatedly removing elements from a list until only one remains. The removal pattern alternates between left-to-right and right-to-left. A brute-force approach would be inefficient for large n. The optimal solution leverages mathematical patterns to efficiently determine the final remaining element.

Approach

The core idea is to observe the pattern of remaining numbers after each iteration. Instead of simulating the removal process, we track the first and last remaining numbers (a1 and an) in each round.

  1. Initialization: a1 starts at 1, an starts at n. step represents the gap between removed numbers (initially 1). cnt tracks the number of remaining elements.

  2. Iteration: The loop continues until only one element remains (cnt > 1). In each iteration:

    • Odd/Even Rounds: The code checks if it's an odd or even iteration (i % 2). This determines the direction of removal (left-to-right or right-to-left).

    • Updating a1 and an: Based on the round and whether the count of remaining elements is odd or even, a1 and an are updated. The updates account for the removal of elements from either end.

    • Updating cnt and step: The number of remaining elements (cnt) is halved after each round. step doubles because the gap between removed elements increases.

  3. Result: After the loop, a1 will hold the last remaining number.

Time and Space Complexity

  • Time Complexity: O(log n). The loop runs approximately log₂(n) times because the number of remaining elements is halved in each iteration. All other operations within the loop are constant time.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space to store variables.

Code Explanation (Python)

class Solution:
    def lastRemaining(self, n: int) -> int:
        a1, an = 1, n
        i, step, cnt = 0, 1, n
        while cnt > 1:
            if i % 2: #Odd iteration (right to left)
                an -= step
                if cnt % 2: #odd number of remaining elements
                    a1 += step
            else: #Even iteration (left to right)
                a1 += step
                if cnt % 2: #odd number of remaining elements
                    an -= step
            cnt >>= 1 #cnt //=2
            step <<= 1 #step *=2
            i += 1
        return a1

The Python code directly implements the algorithm described above. The bitwise operators >>= (right bit shift, equivalent to integer division by 2) and <<= (left bit shift, equivalent to multiplication by 2) are used for efficiency.

The code in Java, C++, and Go follows the same logic and has the same time and space complexity. The only differences are in syntax and some minor variations in how the operations are expressed.