Optimal Division
Medium · 1-D Dynamic Programming · Explanation and code example
Minimize the Denominator
How it works
For positive numbers, maximize the whole expression by minimizing the denominator after the first value. With at least three values, divide the second by all remaining values inside one parenthesized group. One or two inputs need no parentheses.
Steps
- Handle one or two values directly.
- For longer input, format first/(second/third/.../last).
- Return the expression string.
Complexity
- Time: O(L), for L output characters.
- Space: O(L) output storage.
Things to watch for
- Add parentheses only around the denominator group.
- The reasoning relies on the problem’s positive values greater than one.
- Do not add unnecessary parentheses for two values.
Python code example
class Solution:
def optimalDivision(self, nums: list[int]) -> str:
ans = str(nums[0])
if len(nums) == 1:
return ans
if len(nums) == 2:
return ans + '/' + str(nums[1])
ans += '/(' + str(nums[1])
for i in range(2, len(nums)):
ans += '/' + str(nums[i])
ans += ')'
return ans
C++ code example
class Solution {
public:
string optimalDivision(vector<int>& nums) {
string ans = to_string(nums[0]);
if (nums.size() == 1)
return ans;
if (nums.size() == 2)
return ans + "/" + to_string(nums[1]);
ans += "/(" + to_string(nums[1]);
for (int i = 2; i < nums.size(); ++i)
ans += "/" + to_string(nums[i]);
ans += ")";
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.