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