# 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:

```python
nums = [2, 3, 4]
```

then the default expression is:

```python
"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

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | A string expression |
| Operation | Use division between adjacent numbers |
| Rule | Preserve the original order of numbers |
| Goal | Maximize the evaluated value |
| Parentheses | Do not include redundant parentheses |

Example function shape:

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

## Examples

Example 1:

```python
nums = [1000, 100, 10, 2]
```

One possible expression is:

```python
"1000/100/10/2"
```

This evaluates left to right:

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

A better expression is:

```python
"1000/(100/10/2)"
```

Inside the parentheses:

```python
100 / 10 / 2 = 5
```

So the whole expression becomes:

```python
1000 / 5 = 200
```

The answer is:

```python
"1000/(100/10/2)"
```

Example 2:

```python
nums = [2]
```

There is only one number, so the answer is:

```python
"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:

```python
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:

```python
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:

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

For example:

```python
1000 / (100 / 10 / 2)
```

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

```python
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.

| Length | Best expression | Why |
|---|---|---|
| `1` | `nums[0]` | No division exists |
| `2` | `nums[0]/nums[1]` | Parentheses would be redundant |
| `>= 3` | `nums[0]/(nums[1]/nums[2]/...)` | Minimizes the denominator |

For length `2`, this:

```python
"2/(3)"
```

is redundant.

The correct output is:

```python
"2/3"
```

For length `3`, this:

```python
"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:

```python
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:

```python
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:

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

This is larger than:

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

because `d >= 2`.

Therefore, the smallest possible denominator is:

```python
b / c / d / ...
```

and the maximum whole expression is:

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

The algorithm returns exactly this expression, without redundant parentheses.

## Complexity

Let `n` be the length of `nums`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We convert and join the numbers once |
| Space | `O(n)` | The output string has length proportional to the number of input values |

## Implementation

```python
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:

```python
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:

```python
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:

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

The part:

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

turns the remaining numbers into one division chain.

For example:

```python
nums = [1000, 100, 10, 2]
```

becomes:

```python
"100/10/2"
```

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

```python
"1000/(100/10/2)"
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[1000, 100, 10, 2]` | Official-style main case |
| `[2]` | Single number |
| `[2, 3]` | No redundant parentheses |
| `[2, 3, 4]` | Smallest case requiring parentheses |
| `[6, 2, 3, 4]` | Checks the general construction |