Optimal Division

Intuition

The first number is always a numerator and can never be moved into a denominator, so to maximize the result we want the effective denominator to be as small as possible. The second number is always a denominator; every number from the third onward can be pushed into the numerator by wrapping nums[1] through nums[n-1] in a single pair of parentheses. Concretely, nums[0]/(nums[1]/nums[2]/.../nums[n-1]) turns all later divisions into multiplications relative to nums[0], which is provably optimal. When there is only one number no operator exists, and with two numbers the single division is already forced, so neither case needs parentheses.

Algorithm walkthrough

1. 1If the list has a single number, return that number as a string with no operators.
2. 2If it has exactly two numbers, return nums[0]/nums[1] since parentheses would not change the value.
3. 3Otherwise start the result with nums[0] followed by /( to open the grouping.
4. 4Append nums[1], then append /nums[i] for every remaining index i.
5. 5Close the grouping with a single ) to form nums[0]/(nums[1]/.../nums[n-1]).
6. 6Return the assembled expression string.

Implementation

class Solution:
    def optimalDivision(self, nums: List[int]) -> str:
        n = len(nums)
        if n == 1:
            return str(nums[0])
        if n == 2:
            return str(nums[0]) + "/" + str(nums[1])
        rest = "/".join(str(x) for x in nums[1:])
        return str(nums[0]) + "/(" + rest + ")"