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