Leetcode 390 - Elimination Game

Note:

• Every time all nums form an arithemetic progression with different diff.
• Every time the number of num will be 1 / 2 of last time.
• Every time diff will double!
• For example, at first diff of 1,2,3,4,5,6,7,8 is 1.
• Then it becomes 2,4,6,8 which is 2.
• Then it become 2,6 which is 4.
• Note that the head of the progression only changes when
• The number of progression is odd OR
• We start from left.
• We should keep updating the head and eventually it’ll become our ans.

Question:

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.

Example:

Code: