390.md

390. Elimination Game

Solution 1 (time O(n), space O(1))

class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        p1, p2 = 1, n
        step = 1
        cnt = n
        k = 0
        while cnt > 1:
            if k % 2 == 0:
                p1 += step
                if cnt % 2 != 0:
                    p2 -= step
            else:
                p2 -= step
                if cnt % 2 != 0:
                    p1 += step
            step = step * 2
            cnt = cnt // 2
            k += 1
        return p1