553. Optimal Division

Problem Description

You are given an array of integers nums. The array represents a sequence of numbers where each number represents a division operation. You need to add parentheses to the sequence to maximize the result.

For example, if nums = [1000,100,10,2], we can add parentheses to it to be "1000/(100/10/2)". The result is 1000/(100/10/2) = 1000/5 = 200.

Return a string that represents the expression with parentheses that maximizes the division result.

Note:

• The length of the expression should be minimal.
• The order of numbers should not be changed.
• Division between two integers always truncates toward zero.
• The input represents a valid expression that always evaluates to a positive integer.

Example 1:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/5 = 200

Example 2:

Input: nums = [2,3,4]
Output: "2/(3/4)"
Explanation: 2/(3/4) = 2/0.75 = 2.666...

Example 3:

Input: nums = [2]
Output: "2"
Explanation: There is no way to add parentheses to change the result.

Constraints:

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• The expression evaluates to a positive integer.

Python Solution

class Solution:
    def optimalDivision(self, nums: List[int]) -> str:
        if len(nums) == 1:
            return str(nums[0])
        if len(nums) == 2:
            return str(nums[0]) + "/" + str(nums[1])
        
        # For n > 2, the optimal solution is always first/(second/third/...)
        # Because a/(b/c) = (a*c)/b which is larger than (a/b)/c = a/(b*c)
        result = str(nums[0]) + "/(" + str(nums[1])
        for i in range(2, len(nums)):
            result += "/" + str(nums[i])
        result += ")"
        
        return result

Java Solution

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];
        }
        
        // For n > 2, the optimal solution is always first/(second/third/...)
        StringBuilder result = new StringBuilder();
        result.append(nums[0]).append("/(").append(nums[1]);
        
        for (int i = 2; i < nums.length; i++) {
            result.append("/").append(nums[i]);
        }
        result.append(")");
        
        return result.toString();
    }
}

C++ Solution

class Solution {
public:
    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]);
        }
        
        // For n > 2, the optimal solution is always first/(second/third/...)
        string result = to_string(nums[0]) + "/(" + to_string(nums[1]);
        
        for (int i = 2; i < nums.size(); i++) {
            result += "/" + to_string(nums[i]);
        }
        result += ")";
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {string}
 */
var optimalDivision = function(nums) {
    if (nums.length === 1) {
        return nums[0].toString();
    }
    if (nums.length === 2) {
        return nums[0] + "/" + nums[1];
    }
    
    // For n > 2, the optimal solution is always first/(second/third/...)
    let result = nums[0] + "/(" + nums[1];
    
    for (let i = 2; i < nums.length; i++) {
        result += "/" + nums[i];
    }
    result += ")";
    
    return result;
};

C# Solution

public class Solution {
    public string OptimalDivision(int[] nums) {
        if (nums.Length == 1) {
            return nums[0].ToString();
        }
        if (nums.Length == 2) {
            return nums[0] + "/" + nums[1];
        }
        
        // For n > 2, the optimal solution is always first/(second/third/...)
        StringBuilder result = new StringBuilder();
        result.Append(nums[0]).Append("/(").Append(nums[1]);
        
        for (int i = 2; i < nums.Length; i++) {
            result.Append("/").Append(nums[i]);
        }
        result.Append(")");
        
        return result.ToString();
    }
}