Easy P2 solution (Elimination Game)


  • 0
    def lastRemaining(self, n):
        start = step = 1
        while n > 1:
            start += step + (n-2)/2 * 2*step
            n /= 2
            step *= -2
        return start
    

    Instead of switching between leftwards and rightwards phases, I change the procedure to the equivalent and simpler "remove the first number and every other number and then reverse the list". So from 1 2 3 4 5 6 7 8 9 I go to 8 6 4 2. And I represent the list with start, step and n. For example, 8 6 4 2 is represented as start = 8, step = -2, n = 4.

    To get the next start, take one step and then as many double steps as you can. With n numbers, you can make n-1 steps. After that first step, you can further make n-2 steps and thus ⌊(n-2)/2⌋ double steps. That's the formula I used in the code. There are shorter ones like start += ((n|1)-2) * step, but for once I prefer the one that "makes sense" :-)


Log in to reply
 

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