390.Elimination Game

Tags: [math]

Link: https://leetcode.com/problems/elimination-game/?tab=Description

There is a list of sorted integers from 1 ton. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of lengthn.

Example:

Input:
n = 9,

1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

Solution: math

class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('The input is invalid')

        left = True
        remaining = n
        head = 1
        step = 1

        while remaining > 1:
            if left or remaining % 2 == 1:
                head += step

            remaining /= 2
            step *= 2
            left = not left

        return head

Revelation:

• We just need to decide how do we update the 'head'. The final state is that there is only one number left, that should be the head.
• If this turn is from left to right, so the current head will be anyway deleted, so we must update the head to head + step. If the current turn is from right to left and the current number of numbers is odd, the head also must be updated, for example, the current remaining numbers are [2, 4, 6, 8], we remove the numbers 8, 4, so when we get the next turn (from left to right), the head will be still 2, which means we don't need to update the head. But if the current remaining numbers are [2, 4, 6], and we remove the numbers from right to left, so we deleted the 6, 2, and when we hit the next turn(from left to right), the head will be 4, which means we need to update the head to 4 here.

Note:

• Time complexity = O(lgn), n is the given number. Each time remaining is divided by 2, until remaining == 1, so the time complexity = O(lgn).