LeetCode 553: Optimal Division

Problem Restatement

We are given an integer array nums.

The numbers are used in order, with division between adjacent numbers. For example, if:

nums = [2, 3, 4]

then the default expression is:

"2/3/4"

Division is evaluated from left to right unless parentheses change the order.

We may add parentheses anywhere to change the evaluation order. Our goal is to return the expression with the maximum possible value.

The expression should not contain redundant parentheses.

The constraints are 1 <= nums.length <= 10, 2 <= nums[i] <= 1000, and there is only one optimal division for the given input.

Input and Output

Example function shape:

def optimalDivision(nums: list[int]) -> str:
    ...

Examples

Example 1:

nums = [1000, 100, 10, 2]

One possible expression is:

"1000/100/10/2"

This evaluates left to right:

((1000 / 100) / 10) / 2 = 0.5

A better expression is:

"1000/(100/10/2)"

Inside the parentheses:

100 / 10 / 2 = 5

So the whole expression becomes:

1000 / 5 = 200

The answer is:

"1000/(100/10/2)"

Example 2:

nums = [2]

There is only one number, so the answer is:

"2"

First Thought: Try All Parentheses

Since nums.length <= 10, we might think about trying all possible ways to insert parentheses.

For each interval, we could compute the maximum and minimum value that interval can produce. This is a dynamic programming approach.

That works, but it is more complicated than necessary.

This problem has a special structure: every operation is division, and every number is positive.

That structure gives us a much simpler solution.

Key Insight

For an expression like:

a / b / c / d

we want to make the final value as large as possible.

The first number a is always the main numerator. We cannot move it after another number because the order must stay fixed.

So we want to divide a by the smallest possible denominator.

The denominator starts with b.

To make the denominator smaller, we divide b by as many later numbers as possible:

b / c / d

Since all numbers are positive and at least 2, dividing by later numbers makes the denominator smaller.

Therefore, for at least three numbers, the optimal shape is:

a / (b / c / d / ...)

For example:

1000 / (100 / 10 / 2)

This makes 10 and 2 effectively help the numerator, because:

1000 / (100 / 10 / 2)
= 1000 * 10 * 2 / 100

So the best expression puts all numbers after the first inside one parenthesized denominator.

Cases

There are three cases.

For length 2, this:

"2/(3)"

is redundant.

The correct output is:

"2/3"

For length 3, this:

"a/(b/c)"

is necessary because it changes the result.

Algorithm

1. If there is only one number, return it as a string.
2. If there are two numbers, return "a/b".
3. Otherwise:
   1. Convert all numbers after the first into strings.
   2. Join them using "/".
   3. Put that joined expression inside parentheses.
   4. Return first + "/(" + joined_rest + ")".

Correctness

For one number, there is only one possible expression, so returning that number is correct.

For two numbers, there is only one division operation. Parentheses cannot change the value, so returning a/b is correct and non-redundant.

Now consider at least three numbers:

nums = [a, b, c, d, ...]

The first operation involving a must divide a by some expression formed from the remaining numbers. To maximize the whole value, we need to minimize that denominator.

The denominator must begin with b, because the number order cannot change. Since all later numbers are positive and greater than 1, the smallest value we can make from the denominator side is obtained by dividing b by every later number in left-to-right order:

b / c / d / ...

Any parenthesization that puts a later number in a denominator of this denominator makes the denominator larger instead of smaller. For example:

b / (c / d) = b * d / c

This is larger than:

b / c / d = b / (c * d)

because d >= 2.

Therefore, the smallest possible denominator is:

b / c / d / ...

and the maximum whole expression is:

a / (b / c / d / ...)

The algorithm returns exactly this expression, without redundant parentheses.

Complexity

Let n be the length of nums.

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])

        return str(nums[0]) + "/(" + "/".join(map(str, nums[1:])) + ")"

Code Explanation

We first handle the one-number case:

if n == 1:
    return str(nums[0])

There is no division, so the expression is just the number.

Then we handle the two-number case:

if n == 2:
    return str(nums[0]) + "/" + str(nums[1])

No parentheses are needed because there is only one operation.

For three or more numbers, we build:

str(nums[0]) + "/(" + "/".join(map(str, nums[1:])) + ")"

The part:

"/".join(map(str, nums[1:]))

turns the remaining numbers into one division chain.

For example:

nums = [1000, 100, 10, 2]

becomes:

"100/10/2"

Then we wrap it in parentheses and put it after the first number:

"1000/(100/10/2)"

Testing

def run_tests():
    s = Solution()

    assert s.optimalDivision([1000, 100, 10, 2]) == "1000/(100/10/2)"
    assert s.optimalDivision([2]) == "2"
    assert s.optimalDivision([2, 3]) == "2/3"
    assert s.optimalDivision([2, 3, 4]) == "2/(3/4)"
    assert s.optimalDivision([6, 2, 3, 4]) == "6/(2/3/4)"

    print("all tests passed")

run_tests()