MediumArrayMathDynamic Programming

Optimal Division

1 approach, code in every language

You are given a list of positive integers. Written left to right with division between each pair, the expression is evaluated as standard floating-point division and, without parentheses, associates from the left.

You may insert any valid set of parentheses to change the order of evaluation. Return the expression, as a string, that produces the maximum possible value. If several expressions tie, any correct maximal one is acceptable, and you should not add redundant parentheses.

Example 1

Input: nums = [1000,100,10,2]

Output: "1000/(100/10/2)"

Grouping as 1000/(100/10/2) evaluates to 1000/((100/10)/2) = 1000/5 = 200, which is the largest achievable value.

Example 2

Input: nums = [2,3,4]

Output: "2/(3/4)"

2/(3/4) equals 8/3, larger than the default left-to-right value 2/3/4 = 1/6.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 1000

Greedy Parenthesization

The maximum is always nums[0] divided by the product-like chain of the rest, achieved by parenthesizing every number after the first together.

Loading animation…

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

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

Time

O(n)

Space

O(n)

Each number is appended to the output once; the result string length is linear in the input.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free