Elimination Game — LeetCode 390 Python Solution

The problem

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.

Example

Input

n = 9

Output

6

Explanation

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Python solution

class Solution:
    def lastRemaining(self, n: int) -> int:
        a1, an = 1, n
        i, step, cnt = 0, 1, n
        while cnt > 1:
            if i % 2:
                an -= step
                if cnt % 2:
                    a1 += step
            else:
                a1 += step
                if cnt % 2:
                    an -= step
            cnt >>= 1
            step <<= 1
            i += 1
        return a1

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 390. Elimination Game is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems