My Solution to Problem 2 and Explanation


  • 0
    class Solution(object):
        def work(self, n, left_to_right):
            if n == 1:
                return 1
            if left_to_right:
                return 2 * self.work(n//2, False)
            else:
                return 2 * self.work(n//2, True) - (1 if n % 2 == 0 else 0)
        
        def lastRemaining(self, n):
            return self.work(n, True)
    

    After reading some of the posts I realized that this is definitely not the fastest and most concise solution, but it is fast enough to be accepted and easy to comprehend and to come up with:

    First of all, the idea is to use recursion to simulate the game (the work function):

    1. If n is 1, answer is 1
    2. Every pass of elimination will result in an array of size floor(n/2)
    3. Every time the problem is reduced, make sure to reverse the order of elimination
    4. If the current elimination goes from left to right, all odd numbers are going to be eliminated: [1,2,3,4,5,6,7] -> [2,4,6], we can re-number the resulting array to [1,2,3], and the problem is reduced to finding the solution for array [1,2,3] with elimination going from right to left, and it is easy to map the result back with (2 * result)
    5. If the current elimination goes from right to left:
      a) If n is odd, then all odd numbers will be eliminated, everything will be the same as elimination going from left to right
      b) If n is even, all even numbers will be eliminated: [1,2,3,4,5,6,7,8] -> [1,3,5,7], renumber them: [1,2,3,4], find the solution for the new array ([1,2,3,4]) with elimination going from left to right, and the mapping is (2 * result - 1)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.