Python, Straightforward with Explanation (Insightful Approach)


  • 7

    Regardless of parentheses, every element is either in the numerator or denominator of the final fraction. The expression A[0] / ( A[1] / A[2] / ... / A[N-1] ) has every element in the numerator except A[1], and it is impossible for A[1] to be in the numerator, so it is the largest. We must also be careful with corner cases.

    def optimalDivision(self, A):
        A = map(str, A)
        if len(A) <= 2: return '/'.join(A)
        return '{}/({})'.format(A[0], '/'.join(A[1:]))
    

  • 0
    I

    Using str append + is a lot quicker.

    class Solution(object):
        def optimalDivision(self, nums):
            """
            :type nums: List[int]
            :rtype: str
            """
            A = map(str, nums)
            if len(A) <= 2:
                return '/'.join(A)
            return A[0] + '/(' + '/'.join(A[1:]) + ')'
    

    To get the largest result, the numerator has to be as large as possible, while the denominator has to be as small as possible. I just can't think of a case where A[1:] get's any smaller with a different division order instead of the default "one by one" order.


Log in to reply
 

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