[Math] LC 390. Elimination Game

Elimination Game - LeetCode

Goal

• eliminate number and every other numbers from an array
• 1st, 3rd, 5th and other odd number iteration — start from left to right
• 2nd, 4th .. even iteration — start from right to left

Strategy

• in each iteration, double the steps (step*=2)
• in each odd iteration, add the steps to head — which our target index
• why not incrementing the even iterations — no such need as we double the steps already
• return the head (index of the target remaining number) as the final output

Code

class Solution:
    def lastRemaining(self, n: int) -> int:
        left = True
        remain = n
        step = 1
        head = 1
        while remain >1:
            if left or remain%2==1:
                head += step
            remain = remain//2
            step = step*2
            if left:
                left = False
            else:
                left = True
        return head