Optimal Division: Why Greedy Parentheses Always Win
LeetCode 553, Optimal Division, looks like it might need dynamic programming or brute-force enumeration of every possible parenthesization. But there is a surprisingly clean mathematical insight that reduces the entire problem to a single string-formatting step. Once you see it, you will never forget it.
The problem
You are given an array of positive integers. You need to add any number of parentheses to a chained division expression to maximize its value, then return the expression as a string.
For example, given nums = [1000, 100, 10, 2], the default left-to-right evaluation gives 1000 / 100 / 10 / 2 = 0.5. But by adding parentheses you can get 1000 / (100 / 10 / 2) = 200.0. Your job is to find the parenthesization that produces the maximum result.
The key insight
Think about what happens in any chained division. The first number always ends up in the numerator of the final fraction. The second number always ends up in the denominator. No matter how you place parentheses, you cannot change those two facts.
What about the remaining numbers (the third, fourth, and so on)? In the default left-to-right evaluation, they all land in the denominator. But if you wrap everything from the second number onward in a single pair of parentheses, something beautiful happens: a / (b / c / d) simplifies to (a * c * d) / b. The inner division chain b / c / d becomes b / (c * d), and dividing by a fraction means multiplying by its reciprocal. So c and d flip from the denominator into the numerator.
Since all the numbers are positive, moving as many of them as possible into the numerator always increases the result. That means the optimal answer is always a / (b / c / d / ...).
This is a pure math problem disguised as an optimization problem. There is no need for DP, recursion, or enumeration. Recognizing the algebraic identity is the entire solution.
The solution
class Solution:
def optimalDivision(self, nums: list[int]) -> str:
if len(nums) == 1:
return str(nums[0])
if len(nums) == 2:
return f"{nums[0]}/{nums[1]}"
inner = "/".join(str(x) for x in nums[1:])
return f"{nums[0]}/({inner})"
The logic breaks down into three cases. If there is only one number, just return it. If there are two numbers, the only option is a/b. For three or more numbers, wrap everything after the first number in parentheses: a/(b/c/d/...). That is always the maximum.
Step-by-step walkthrough
optimalDivision([1000, 100, 10, 2]):Step 1: Identify positions
In any chained division a / b / c / d, the first element (a) is always in the numerator and the second element (b) is always in the denominator. No amount of parentheses can change that.
Step 2: Maximize the numerator
Every element after the second (c, d, ...) is in the denominator by default. To maximize the result, you want them in the numerator instead. Wrapping them in parentheses after b achieves exactly this: a / (b / c / d) = a * c * d / b.
Step 3: Build the output string
For a single number, return it directly. For two numbers, return "a/b". For three or more, wrap everything from the second number onward in parentheses: "a/(b/c/d/...)".
The greedy parenthesization is always optimal. No dynamic programming or brute-force search needed.
The greedy parenthesization works for every input. No matter how many numbers you have, the answer always follows the same pattern.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Greedy (math insight) | O(n) | O(n) |
You iterate through the array once to build the output string. The space is O(n) for the resulting string. There is no additional data structure needed.
The building blocks
Division identity
The core reusable identity here is: a / (b / c) = a * c / b. Dividing by a fraction is the same as multiplying by its reciprocal. This extends to chains: a / (b / c / d) = a * c * d / b. Any time you see nested division in an interview problem, this identity might simplify things dramatically.
When a problem involves division or fractions, look for algebraic simplifications before reaching for DP or brute force. Many "optimization" problems over arithmetic expressions have closed-form solutions.
Edge cases
- Single number: return it as-is, no division to perform.
- Two numbers: only one possible expression
a/b, no parentheses needed. - All equal numbers: the formula still works. For
[k, k, k, k], the result isk/(k/k/k) = k * k * k / k = k^2. The greedy approach handles this correctly. - Large numbers: since you are only building a string (not computing the actual value), overflow is not a concern.
From understanding to recall
The key to remembering this problem is the algebraic identity. Once you internalize that dividing by a chain of divisions flips the inner terms into the numerator, the solution writes itself. Practice recalling the identity from scratch: given a / (b / c / d), can you simplify it to (a * c * d) / b without looking it up? Spaced repetition on that single fact is all you need.
Related posts
- Pow(x, n) - Another math problem where the key insight simplifies the solution dramatically
- Multiply Strings - Math operations on number representations
- Divide Two Integers - Division mechanics without using the division operator
This is the kind of problem that separates pattern recognizers from brute-force coders. CodeBricks helps you build the mathematical intuition so these insights come naturally during interviews.