Optimal Division

Med

#0536Time: O(N^3). There are `O(N^2)` possible subproblems (states `(i, j)`). To compute each state, we iterate through `O(N)` possible split points `k`. The recursive calls are `O(1)` due to memoization. Thus, the total time complexity is `O(N^2 * N) = O(N^3)`.Space: O(N^3). The memoization tables `memoMax` and `memoMin` require `O(N^2)` space. However, each entry in the table stores a string expression, which can have a length of up to `O(N)`. This leads to a total space complexity of `O(N^2 * N) = O(N^3)`.

Patterns

Math Dynamic Programming

Data structures

Array

Prompt

You are given an integer array nums. The adjacent integers in nums will perform the float division.

For example, for nums = [2,3,4], we will evaluate the expression "2/3/4".

However, you can add any number of parenthesis at any position to change the priority of operations. You want to add these parentheses such the value of the expression after the evaluation is maximum.

Return the corresponding expression that has the maximum value in string format.

Note: your expression should not contain redundant parenthesis.

Example 1:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Example 2:

Input: nums = [2,3,4]
Output: "2/(3/4)"
Explanation: (2/(3/4)) = 8/3 = 2.667
It can be shown that after trying all possibilities, we cannot get an expression with evaluation greater than 2.667

Constraints:

1 <= nums.length <= 10
2 <= nums[i] <= 1000
There is only one optimal division for the given input.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively explores all possible ways to place parentheses to find the optimal solution. We can define a recursive function that computes the maximum and minimum possible values for any sub-array nums[i...j]. To avoid the exponential complexity of pure recursion, we use memoization (a top-down dynamic programming technique) to store and reuse the results for subproblems.

Algorithm

Define a recursive function, say solve(i, j), that computes the maximum and minimum possible values for the sub-array nums[i...j].
The state for our recursion/DP is the pair of indices (i, j).
Use two 2D arrays, memoMax[n][n] and memoMin[n][n], to store the computed results (memoization) to avoid redundant calculations. Each entry will store both the computed value and the corresponding string expression.
Base Case: If i == j, the sub-array has only one element. The maximum and minimum values are both nums[i], and the expression is simply String.valueOf(nums[i]).
Recursive Step: To compute the result for (i, j), we iterate through all possible split points k from i to j-1. A split at k corresponds to the expression (nums[i]...nums[k]) / (nums[k+1]...nums[j]).
- To find the maximum value for (i, j), we need to maximize the numerator and minimize the denominator. So, for each k, we calculate solve(i, k).maxValue / solve(k+1, j).minValue.
- To find the minimum value for (i, j), we need to minimize the numerator and maximize the denominator. So, for each k, we calculate solve(i, k).minValue / solve(k+1, j).maxValue.
We keep track of the split k that yields the best result and construct the expression string accordingly.
String Construction: When combining two sub-expressions expr1 and expr2 as expr1 / expr2, if expr2 corresponds to a sub-array of length greater than 1 (i.e., it already contains a division), it must be enclosed in parentheses to ensure correct precedence. For example, A / (B/C).
The final answer is the string part of the result of solve(0, n-1).maxValue.

Walkthrough

We define two mutually recursive functions, getMax(i, j) and getMin(i, j), which compute the maximum and minimum value obtainable from the sub-array nums[i...j], respectively. They also return the string expression that yields this value. The state for our recursion is (i, j), and we use two 2D arrays, memoMax and memoMin, to store the computed results.

Base Case: If i == j, the sub-array has one element. The max and min values are both nums[i], and the expression is just the number itself as a string.

Recursive Step: To compute getMax(i, j), we iterate through all possible split points k from i to j-1. A split at k divides the expression into (nums[i]...nums[k]) / (nums[k+1]...nums[j]). To maximize this division, we must maximize the numerator and minimize the denominator. So, we recursively call getMax(i, k) and getMin(k+1, j). We do this for all k and take the overall maximum. Similarly, to compute getMin(i, j), we need to minimize the numerator and maximize the denominator, so we call getMin(i, k) and getMax(k+1, j).

When constructing the expression string from expr1 and expr2, we add parentheses around expr2 if it corresponds to a sub-array of length greater than 1 to maintain the correct order of operations. The final answer is the string returned by getMax(0, n-1).

1class Solution {2    class Result {3        double value;4        String str;5        Result(double v, String s) {6            this.value = v;7            this.str = s;8        }9    }10 11    private Result[][] memoMax;12    private Result[][] memoMin;13    private int[] nums;14 15    public String optimalDivision(int[] nums) {16        this.nums = nums;17        int n = nums.length;18        memoMax = new Result[n][n];19        memoMin = new Result[n][n];20        return findMax(0, n - 1).str;21    }22 23    private Result findMax(int i, int j) {24        if (memoMax[i][j] != null) {25            return memoMax[i][j];26        }27        if (i == j) {28            return new Result(nums[i], String.valueOf(nums[i]));29        }30 31        Result maxRes = new Result(-1.0, "");32 33        for (int k = i; k < j; k++) {34            Result left = findMax(i, k);35            Result right = findMin(k + 1, j);36            double val = left.value / right.value;37            if (val > maxRes.value) {38                maxRes.value = val;39                String rightStr = right.str;40                if (k + 1 < j) { // Denominator is a complex expression41                    rightStr = "(" + rightStr + ")";42                }43                maxRes.str = left.str + "/" + rightStr;44            }45        }46        return memoMax[i][j] = maxRes;47    }48 49    private Result findMin(int i, int j) {50        if (memoMin[i][j] != null) {51            return memoMin[i][j];52        }53        if (i == j) {54            return new Result(nums[i], String.valueOf(nums[i]));55        }56 57        Result minRes = new Result(Double.MAX_VALUE, "");58 59        for (int k = i; k < j; k++) {60            Result left = findMin(i, k);61            Result right = findMax(k + 1, j);62            double val = left.value / right.value;63            if (val < minRes.value) {64                minRes.value = val;65                String rightStr = right.str;66                if (k + 1 < j) { // Denominator is a complex expression67                    rightStr = "(" + rightStr + ")";68                }69                minRes.str = left.str + "/" + rightStr;70            }71        }72        return memoMin[i][j] = minRes;73    }74}

Complexity

Time

O(N^3). There are `O(N^2)` possible subproblems (states `(i, j)`). To compute each state, we iterate through `O(N)` possible split points `k`. The recursive calls are `O(1)` due to memoization. Thus, the total time complexity is `O(N^2 * N) = O(N^3)`.

Space

O(N^3). The memoization tables `memoMax` and `memoMin` require `O(N^2)` space. However, each entry in the table stores a string expression, which can have a length of up to `O(N)`. This leads to a total space complexity of `O(N^2 * N) = O(N^3)`.

Trade-offs

Pros

Guaranteed to find the correct optimal solution by exploring all valid parenthesizations.
It's a general method that can be adapted for similar problems with different operators or constraints.

Cons

The time and space complexity are high (O(N^3)), making it inefficient for larger constraints.
The implementation is more complex compared to the simpler greedy approach.

A closer analysis of the expression x1 / x2 / ... / xn reveals a simple greedy strategy. To maximize a fraction, we aim to maximize the numerator and minimize the denominator. The structure of the division chain allows for a straightforward way to achieve this, leading to a highly efficient solution.

Algorithm

Handle the edge cases first. If the array has 1 or 2 elements, no parentheses are needed.
- If n == 1, return nums[0].
- If n == 2, return nums[0] + "/" + nums[1].
If the array has more than 2 elements (n > 2), apply the greedy strategy.
Construct the result string by taking the first element nums[0], followed by "/(".
Iterate from the second element nums[1] to the last element nums[n-1], appending them to the string, separated by /.
Finally, append the closing parenthesis ")".
Return the constructed string.

Walkthrough

The expression we want to maximize is x1 / x2 / x3 / ... / xn. We can group this as x1 / D, where D is the result of evaluating x2 / x3 / ... / xn with some parentheses. To maximize the total value, we must minimize the value of the denominator D (since x1 is fixed and all numbers are positive).

Let's analyze D = x2 / x3 / ... / xn. Since all numbers are > 1, to minimize this expression, we want to divide x2 by the largest possible number we can form from x3, ..., xn. The largest possible denominator is formed by multiplying all subsequent numbers together: x3 * x4 * ... * xn.

Conveniently, the standard left-to-right evaluation of x2 / x3 / ... / xn (i.e., ((x2 / x3) / x4) ...) results in x2 / (x3 * x4 * ... * xn). This gives the smallest possible value for D.

Therefore, the optimal strategy is to group the entire sub-expression from the second number onwards. The resulting expression is x1 / (x2 / x3 / ... / xn). This maximizes the overall value.

For small arrays (n <= 2), no parentheses are needed. For n > 2, we apply the pattern x1/(x2/.../xn).

1public class Solution {2    public String optimalDivision(int[] nums) {3        int n = nums.length;4        if (n == 1) {5            return String.valueOf(nums[0]);6        }7        if (n == 2) {8            return nums[0] + "/" + nums[1];9        }10 11        StringBuilder sb = new StringBuilder();12        sb.append(nums[0]).append("/(");13        for (int i = 1; i < n; i++) {14            sb.append(nums[i]);15            if (i < n - 1) {16                sb.append("/");17            }18        }19        sb.append(")");20 21        return sb.toString();22    }23}

Complexity

Time

O(N). We iterate through the input array once to build the result string.

Space

O(N). We use a `StringBuilder` to construct the result string. The length of the final string is proportional to the number of elements and their digits, which is `O(N)`.

Trade-offs

Pros

Extremely efficient, with linear time and space complexity.
The implementation is very simple and concise.
It directly constructs the single optimal solution without exploring other possibilities.

Cons

The logic is based on a specific mathematical property of division and positive numbers, so it's not a general-purpose algorithm for expression evaluation problems.

Solutions

Solution

1class Solution {2public3  String optimalDivision(int[] nums) {4    int n = nums.length;5    if (n == 1) {6      return nums[0] + "";7    }8    if (n == 2) {9      return nums[0] + "/" + nums[1];10    }11    StringBuilder ans = new StringBuilder(nums[0] + "/(");12    for (int i = 1; i < n - 1; ++i) {13      ans.append(nums[i] + "/");14    }15    ans.append(nums[n - 1] + ")");16    return ans.toString();17  }18}

1class Solution {2public:3  string optimalDivision(vector<int> &nums) {4    int n = nums.size();5    if (n == 1)6      return to_string(nums[0]);7    if (n == 2)8      return to_string(nums[0]) + "/" + to_string(nums[1]);9    string ans = to_string(nums[0]) + "/(";10    for (int i = 1; i < n - 1; i++)11      ans.append(to_string(nums[i]) + "/");12    ans.append(to_string(nums[n - 1]) + ")");13    return ans;14  }15};

1class Solution:2    def optimalDivision(self, nums: List[int]) -> str: n = len(nums) if n == 1: return str(nums[0]) if n == 2: return f ' { nums [ 0 ] } / { nums [ 1 ] } ' return f ' { nums [ 0 ] } /( { "/" . join ( map ( str , nums [ 1 : ])) } )'

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem