553. Optimal Division

Approach 1: I don't whether its fair to call it stupid or not

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

The first number definitely has to be in the numerator of the final division. Moreover all the numbers are greater than 2, which means division of one number by the other will always result in a smaller number.

So the naiive approach is to simply maximize numerator while minimizing denominator. Since the first number is the only one in the numerator at first we don't want to reduce it further by dividing it with any other number.

Our best approach would be to just divide the first number by the result of division of all the other numbers.

i.e. in a list of [2,4,5,7,8,9] our best answer would inevitably be: 2/(4/5/6/7/8/9) since this way the numerator is maximized [we're not dividing it by anything] and denominator is minimized.

Time Complexity: O(n)

Space Complexity: O(n)