Problem statement

https://leetcode.com/problems/elimination-game/

Solution

Note, that at each iteration we have arithmetic progression. Let us keep only 4 numbers on each iteration begin, step, end, direction, where direction is either 0 or 1 for left to right and from right to left movement correspondingly. We can update these for number in O(1), for example for direction = 0: (a, step, b, 0) -> (a+step, 2*step, b-(b-a-step)%(2*step), 1), similar for another direction. We always keep begin <= end. Here (b - a - step) % (2*step) is equal to 0 or step and used to calculate if we need to take the last element or not depending of parity.

Complexity

So, overall complexity will be O(log n), because we need to do at most log n iterations. It can be done in recursive way with oneliner as well.

Code

class Solution:
    def lastRemaining(self, n):
        def one_step(a, step, b, ind):
            if ind == 0:
                return (a + step, 2*step, b - (b-a-step) % (2*step), 1)
            if ind == 1:
                return (a + (b-a-step) % (2*step), 2*step, b-step, 0)
        
        a, step, b, ind = 1, 1, n, 0
        while a != b:
            a, step, b, ind = one_step(a, step, b, ind)            
        return a