Simple and fast python solution for P2 elimination game


  • 0
    C

    Apparently, you can't use brute force. I tried it and got time limit exceeded when n = 4169.

    The idea is simple: it's like a binary search, each operation cut the total number by half. You just need to document the first number after each operation. Flag is used to remember whether it's a left or right elimination. If it's a left elimination , first number += step. If it's right elimination, it depends on the total remaining number: If it's odd, first number += step, otherwise, the first number remains unchanged. Step = 2**(times of elimination-1).

    class Solution(object):
        def lastRemaining(self, n):
            """
            :type n: int
            :rtype: int
            """
            count, flag, res = 0, 0, 1
            while n > 1:
                n, v = divmod(n, 2)
                v += n
                temp = 2 ** count
                if not flag:
                    res += temp
                    flag = 1
                else:
                    if v != n: res += temp
                    flag = 0
                count += 1 
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.