Optimal Division

medium array math dp

Problem

Insert any number of parentheses into nums[0]/nums[1]/.../nums[n-1] so the resulting division value is maximal. Return that expression as a string.

Inputnums = [1000,100,10,2]

Output"1000/(100/10/2)"

The only way to make it bigger is to make the divisor smaller; group everything after nums[0].

nums

def optimal_division(nums):
    if len(nums) == 1: return str(nums[0])
    if len(nums) == 2: return f"{nums[0]}/{nums[1]}"
    return f"{nums[0]}/(" + "/".join(map(str, nums[1:])) + ")"

function optimalDivision(nums) {
  if (nums.length === 1) return String(nums[0]);
  if (nums.length === 2) return `${nums[0]}/${nums[1]}`;
  return `${nums[0]}/(${nums.slice(1).join("/")})`;
}

class Solution {
    public String optimalDivision(int[] nums) {
        if (nums.length == 1) return String.valueOf(nums[0]);
        if (nums.length == 2) return nums[0] + "/" + nums[1];
        StringBuilder sb = new StringBuilder(); sb.append(nums[0]).append("/(");
        for (int i = 1; i < nums.length; i++) { sb.append(nums[i]); if (i + 1 < nums.length) sb.append('/'); }
        sb.append(')'); return sb.toString();
    }
}

string optimalDivision(vector& nums) {
    if (nums.size() == 1) return to_string(nums[0]);
    if (nums.size() == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
    string s = to_string(nums[0]) + "/(";
    for (int i = 1; i < (int)nums.size(); i++) { s += to_string(nums[i]); if (i + 1 < (int)nums.size()) s += '/'; }
    s += ')'; return s;
}

Explanation

This problem looks like it needs heavy dynamic programming, but there is a clean shortcut: for three or more numbers the best answer is always nums[0]/(nums[1]/nums[2]/.../nums[n-1]).

The trick is that nums[0] is always the numerator and nums[1] is always a divisor no matter where you put parentheses — those two can't be moved. To make the overall value as large as possible, you want the total divisor to be as small as possible. Grouping all of nums[1..] together turns them into nums[1]/nums[2]/.../nums[n-1], which is the smallest divisor you can form (every later number ends up multiplying the numerator).

So the code just handles the tiny cases: length 1 returns the single number, length 2 returns a/b (nothing to parenthesize), and otherwise it wraps everything after the first number in parentheses.

Example: nums = [1000,100,10,2]. The output is "1000/(100/10/2)". The inner part equals 100/10/2 = 5, so the whole thing is 1000/5 = 200, the maximum achievable.

Building the string is a single pass over the numbers, so it runs in linear time and space.

Time: O(n) Space: O(n)