Building an efficient algorithm for "Eliminating Game"

Question

I was solving this Elimination Game problem.

First, I tried by brute-force;

• eliminated numbers from start with distance $2$ (i.e element after the next one)
• reversed the list
• eliminated numbers from start by with distance $2$
• reversed the list...

Finally, returned the last remaining element. However, not surprisingly, this raised "Time Limit Exceeded".

Here is the Python code for this:

def lastRemaining(n: int) -> int:
        nums = [i for i in range(1, n + 1)]
        l = len(nums)
        while l != 1:
            for i in range(0, len(nums), 1):
                if i < len(nums): 
                    nums.remove(nums[i])
                    l -= 1
            nums.reverse()
        return nums[0]

Then, I searched for a better solution and found the following:

def lastRemaining(n: int) -> int:
        if n == 1: return 1
        return (n//2 - lastRemaining(n//2) + 1) * 2

and it works. This is mathematically written as $$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ I've verified this for some values of $n$. Nonetheless, I need help on proving that this algorithm works for every case.

Any help is appreciated.

Answer 1

The first case $n=1$ is obvious. For the second case, note that what you are doing is basically running the first iteration and solving the problem on the remaining (which is $2, 4, 6, ... 2⌊n/2⌋$) - well, almost. You do it in a reverse order, which is why you have $⌊n/2⌋-f(⌊n/2⌋)+1$ instead of $f(⌊n/2⌋)$ Here, note that you are actually returning the order of the "last number" and not its value, which would be equivalent in the original problem. Therefore we multiply by $2$ at the end in order to get the value of the "last number" which we know the order of.