Easy to understand verbose python code (Divide and Conquer)


  • 0
    S
    class Solution(object):
        def helper_odd(self, n , dir):
            if n == 3 or n == 1:
                return (n+1)/2
            val = (n-1)/2
            if val%2 == 0:
                ans = self.helper_even(val, self.direcs[dir])
            else:
                ans = self.helper_odd(val, self.direcs[dir])
            return 2 * ans
        
        def helper_even(self, n ,dir):
            if n == 2:
                return 2 if dir == 'left-to-right' else 1
            val = n / 2
            if val % 2 == 0:
                ans = self.helper_even(val, self.direcs[dir])
            else:
                ans = self.helper_odd(val, self.direcs[dir])
            return 2 * ans if dir == 'left-to-right' else (2 * ans) - 1
            
        def lastRemaining(self, n):
            """
            :type n: int
            :rtype: int
            """
            self.direcs = {'left-to-right':'right-to-left', 'right-to-left':'left-to-right'}
            dir = 'left-to-right'
            return self.helper_odd(n, dir) if n%2 else self.helper_even(n, dir)
            
    

    Explanation:
    I know the answer if n = 1, 2 or 3.
    Now the question is that if I know the answer when I have 'n' numbers in my list, how to find the answer when I have '2n' or '2n+1' numbers in my list.
    If answer for 'n' is x, then:
    answer for '2n+1' would be 2x
    answer for '2n' would be 2x if we are eliminating from left to right
    answer for '2n' would be 2x -1 if we are eliminating from right to left


  • 0
    S
    This post is deleted!

Log in to reply
 

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