Optimal Division

Medium
1204.

Optimal Division

Optimal Division is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

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 <= 10
  • 2 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {string}
 */
var optimalDivision = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 10
  • 2 <= nums[i] <= 1000

Hints for Optimal Division

  1. Hint 1

    However you parenthesise, the first number is always in the numerator and the second always in the denominator.

  2. Hint 2

    The best you can hope for is every other number in the numerator.

  3. Hint 3

    a/(b/c/d/…) equals a·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

  1. If there is one number, return it.
  2. If there are two, return a/b — no parentheses can change it.
  3. 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