Optimal Division — Solution in Python, Java & C++
Optimal Division solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Optimal Division is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The integers of nums are written in order with a division sign between neighbours, for example [8,2,4] gives 8/2/4, which is evaluated left to right as (8/2)/4 = 1 using exact (real-number) division.
You may insert any number of pairs of parentheses to change the order of evaluation. Return the expression with the largest value, written as a string with the numbers in their original order, / between them, and no redundant parentheses (a pair that does not change the evaluation order must be left out). No spaces.
The inputs are such that this expression is unique.
Example 1
Input: nums = [12,3,2]
Output: "12/(3/2)"
Explanation: `12/(3/2) = 8`, while `12/3/2 = 2`.
Example 2
Input: nums = [7,4]
Output: "7/4"
Example 3
Input: nums = [25]
Output: "25"
Constraints
1 <= nums.length <= 102 <= nums[i] <= 1000
Hints for Optimal Division
Hint 1
However you parenthesise, the first number is always in the numerator and the second always in the denominator.
Hint 2
The best you can hope for is every other number in the numerator.
Hint 3
a/(b/c/d/…)equalsa·c·d·…/b— and it needs only one pair of parentheses.
How to solve Optimal Division
Since every number is at least 2, the value is maximised by dividing nums[0] by the smallest possible denominator, and nums[1]/nums[2]/…/nums[n−1] evaluated left to right is exactly that: it keeps only nums[1] in the denominator.
Approach
- If there is one number, return it.
- If there are two, return
a/b— no parentheses can change it. - Otherwise return
nums[0] + "/(" + nums[1..].join("/") + ")".
Why it works
In any parenthesisation nums[0] ends up in the numerator and nums[1] in the denominator (it is the first number to the right of the first division). The expression a/(b/c/…/z) simplifies to a·c·…·z / b, which puts every other number in the numerator — no expression can do better, and because every number is at least 2 this is a strict improvement whenever there are three or more numbers. The parentheses are not redundant (removing them gives a/b/c/…), and none inside are needed because left-to-right is already the order wanted. An interval DP over (max, min) pairs reaches the same value in O(n^3) — useful for checking, unnecessary for solving.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Two numbers must not get parentheses:
7/(4)is redundant. - Wrapping the whole tail in more parentheses, like
a/((b/c)/d), is redundant too. - Building the DP is correct but over-engineered — the greedy form is provably optimal.
Reference solution
Python
from typing import List
def optimalDivision(nums: List[int]) -> str:
parts = [str(x) for x in nums]
if len(parts) <= 2:
return "/".join(parts)
return parts[0] + "/(" + "/".join(parts[1:]) + ")"Java
public static String optimalDivision(int[] nums) {
StringBuilder sb = new StringBuilder();
sb.append(nums[0]);
if (nums.length == 1) return sb.toString();
if (nums.length == 2) return sb.append('/').append(nums[1]).toString();
sb.append("/(");
for (int i = 1; i < nums.length; i++) {
if (i > 1) sb.append('/');
sb.append(nums[i]);
}
return sb.append(')').toString();
}C++
string optimalDivision(vector<int>& nums) {
int n = (int)nums.size();
string res = to_string(nums[0]);
if (n == 1) return res;
if (n == 2) return res + "/" + to_string(nums[1]);
res += "/(";
for (int i = 1; i < n; i++) {
if (i > 1) res += "/";
res += to_string(nums[i]);
}
return res + ")";
}JavaScript
var optimalDivision = function(nums) {
if (nums.length <= 2) return nums.join("/");
return nums[0] + "/(" + nums.slice(1).join("/") + ")";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming