2/24/2021

[LeetCode] 390. Elimination Game

 Problem: https://leetcode.com/problems/elimination-game/


class Solution:
    def lastRemaining(self, n: int) -> int:
        # track the head number.
        # when total remaining number becomes 1, head is the only number left.
        
        left = True
        remaining = n
        
        step = 1
        head = 1 
        
        while remaining > 1:
            if left:
                # remove number from left
                # move head to next number
                head += step
            else:
                # remove number from right
                if remaining & 1:
                    # when total remaining number is odd
                    # move head to next number
                    # like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
                    head += step
                else:
                    # when total remaining number is even
                    # head won't change
                    # like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2
                    pass
            
            # every time remove half of the numbers
            remaining = remaining // 2
            
            # expand step
            step = step * 2
            
            # change direction
            left = not left
        
        return head