2232. Minimize Result by Adding Parentheses to Expression

MediumStringEnumeration

Problem Description

You are given an expression in the form of <num1>+<num2>, where both <num1> and <num2> are positive integers. The goal is to add a single pair of parentheses to the expression to minimize its value after the addition is performed. There is a requirement that the left parenthesis has to be placed somewhere to the left of the '+' sign, and the right parenthesis has to be placed somewhere to the right of the '+' sign.

The task is to modify the expression by adding these parentheses such that the computed result is the smallest possible value, and return the modified expression as a string. If there are several ways to insert the parentheses that yield the same minimum value, any of those valid expressions can be returned.

The problem ensures that the result before and after inserting the parentheses will both fit within the bounds of a signed 32-bit integer.

Intuition

The intuition behind the solution stems from the fundamental properties of arithmetic, particularly the effect of the order of operations (parentheses, exponents, multiplication and division, addition and subtraction - PEMDAS) on the outcome of expressions. Placing parentheses around a part of an expression changes the order in which operations are performed.

The given expression <num1>+<num2> will always result in addition. However, by strategically placing a pair of parentheses, we can create a situation where a multiplication occurs before the addition, which can potentially lower the total value. For example, if num1 = 2 and num2 = 3, the expression 2+3 would normally evaluate to 5. But by changing it to 2+(3), it still evaluates to 5. However, changing it to (2+3) would still evaluate to 5. The point here is to see if, by splitting either num1 or num2 and performing multiplication with one of those split parts, we can reduce the overall value.

The solution involves iterating through all possible positions where the parentheses could be placed in the expression, calculating the result for each arrangement, and keeping track of the smallest result along with the corresponding arrangement. Specifically, we split the num1 and num2 into two parts at different positions: num1 is split into a and b, and num2 is split into c and d. We then calculate the result by computing (b+c)*a*d. We compare this result to the minimum value we've seen so far and update the minimum and the answer when we find a smaller value.

By iterating through all possible splits for num1 and num2, we ensure that we cover all possible combinations of parentheses placements. This brute-force approach guarantees that we find the smallest possible expression value.

Solution Approach

The implementation uses a brute-force strategy to enumerate all possibilities for where to place a pair of parentheses in the given expression. It does so by splitting the expression around the '+' sign to yield two substrings: l which corresponds to <num1>, and r which corresponds to <num2>. These substrings represent the left and right parts of the expression around the '+' sign, respectively.

The algorithm iteratively partitions each of these substrings l and r into two parts: one up to a certain position, which will be inside the parentheses and be added to each other, and another part from that position to the end of the string, which will be used for multiplication.

A couple of nested loops are used to test every possible pair of positions to place the parentheses. For the string l, valid split positions range from [0, m) where m is the length of l. For the string r, valid split positions range from [0, n) where n is the length of r. For each combination of i in l and j in r, we consider the calculation:

c is the sum of the integers formed by the substrings l[i:] and r[:j+1].
a multiplies the result with the integer formed by substring l[:i], defaulting to 1 if i is 0 (meaning no substring).
b multiplies the result with the integer formed by substring r[j+1:], defaulting to 1 if j is n-1 (meaning no substring).

The total expression value for the current placement of parentheses is then a * b * c. This value is compared to the current minimum value mi, and if it is smaller, the minimum value is updated, and the corresponding string representation ans is formed using f-string formatting. This representation inserts parentheses at the calculated positions within l and r.

After all possible placements for the parentheses have been tested, the ans that corresponds to the smallest found value mi is returned.

This approach guarantees that all placements are considered and that the optimal result is always found. The choice of brute-force is suitable here due to the small size of the problem space, and such an approach is straightforward to implement and understand, despite not being the most efficient in terms of computational complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach with an example, let's take the expression 123+4567. We want to insert a pair of parentheses in such a way that the sum of the numbers is minimized after performing the operations within parentheses first.

Following the described brute-force strategy, we'll split the expression at the '+' sign. This gives us num1 = "123" and num2 = "4567". We will consider all possible ways to split these strings into two parts and compute the resulting expression as per the given approach.

For num1, we have 3 split positions:

("","123") → We can't place parentheses as there is no number before the '+'.
("1","23") → The calculation would be 1 * ((23+4567)).
("12","3") → The calculation would be 12 * ((3+4567)).
("123","") → The calculation would be 123 * ((+4567)), which is essentially 123 + 4567, the original expression without any meaningful parentheses.

For num2, we also have 4 split positions:

("","4567") → We can't place parentheses as there is no number after the '+'.
("4","567") → The calculation would be ((123+4)) * 567.
("45","67") → The calculation would be ((123+45)) * 67.
("456","7") → The calculation would be ((123+456)) * 7.
("4567","") → Same as the case with num1, no meaningful parentheses can be inserted.

Now we evaluate each combination to find the minimum value. For example, let's consider splitting num1 at 2 ("12","3") and num2 at 2 ("45","67"), which implies we insert parentheses to get (12+45)*3*67. Performing the operations inside the parentheses first gives us (57)*3*67.

Let's compute the result:

Inside parentheses 12+45 = 57
Multiplying by the remaining parts: 57 * 3 * 67 = 11457

As we loop through all combinations, we find the one that gives us the smallest result. For simplicity, let's assume that in our example (12+45)*3*67 gives us the smallest result. Then, we return this manipulated string representation as our answer: (12+45)*3*67.

We perform a similar brute-force test for all the other possible splits of num1 and num2, keep track of the smallest result, and update our answer each time we find a new smallest result. By the end of our nested loops, we will have considered every possible placement for parentheses and arrive at the minimum possible evaluated expression, which we return.

Solution Implementation

1class Solution:
2    def minimizeResult(self, expression: str) -> str:
3        # Split the input string into two parts separated by the '+'
4        left_part, right_part = expression.split("+")
5      
6        # Get the length of the left and right parts
7        left_len = len(left_part)
8        right_len = len(right_part)
9      
10        # Initialize minimum value to positive infinity
11        min_value = float('inf')  # or use `math.inf`
12      
13        # Initialize the answer string
14        answer = ""
15      
16        # Iterate through all possible non-empty prefixes of left_part
17        for i in range(left_len):
18            # Iterate through all possible non-empty suffixes of right_part
19            for j in range(right_len):
20                # Calculate the sum of the chosen parts and evaluate the expression
21                current_sum = int(left_part[i:]) + int(right_part[:j+1])
22              
23                # Take the prefix of left_part and the suffix of right_part;
24                # If empty (at the extremities), their value should be 1 (neutral for multiplication)
25                left_prefix_value = 1 if i == 0 else int(left_part[:i])
26                right_suffix_value = 1 if j == right_len - 1 else int(right_part[j+1:])
27              
28                # Calculate the temporary result of the current configuration
29                current_result = left_prefix_value * right_suffix_value * current_sum
30              
31                # If the current result is less than the previous minimum, update it
32                if current_result < min_value:
33                    min_value = current_result
34                  
35                    # Format and update the answer string to represent the current minimum expression
36                    # Surround the chosen parts with parentheses to indicate their placement in the expression
37                    answer = f"{left_part[:i]}({left_part[i:]}+{right_part[:j+1]}){right_part[j+1:]}"
38      
39        # Return the formatted answer string
40        return answer
41

1class Solution {
2    public String minimizeResult(String expression) {
3        // Find the index of the '+' in the expression
4        int plusIndex = expression.indexOf('+');
5      
6        // Split the expression into left and right parts
7        String leftPart = expression.substring(0, plusIndex);
8        String rightPart = expression.substring(plusIndex + 1);
9      
10        // Get the lengths of the left and right parts
11        int leftLength = leftPart.length();
12        int rightLength = rightPart.length();
13      
14        // Initialize minimum value to the largest possible integer
15        int minResult = Integer.MAX_VALUE;
16      
17        // Variable to store the answer string with minimum value
18        String answer = "";
19      
20        // Check every possible pair of parentheses
21        for (int i = 0; i < leftLength; ++i) {
22            for (int j = 0; j < rightLength; ++j) {
23              
24                // Calculate the sum inside the parentheses
25                int parenthesizedSum = Integer.parseInt(leftPart.substring(i)) +
26                                       Integer.parseInt(rightPart.substring(0, j + 1));
27              
28                // Compute the left multiplication factor
29                int leftMulFactor = i == 0 ? 1 : Integer.parseInt(leftPart.substring(0, i));
30              
31                // Compute the right multiplication factor
32                int rightMulFactor = j == rightLength - 1 ? 1 : Integer.parseInt(rightPart.substring(j + 1));
33              
34                // Calculate the total for the current partition
35                int total = leftMulFactor * rightMulFactor * parenthesizedSum;
36              
37                // Check if the total is the new minimum
38                if (total < minResult) {
39                    // Update the minimum result
40                    minResult = total;
41                  
42                    // Format answer string with the current minimum partition
43                    answer = String.format("%s(%s+%s)%s", 
44                                leftPart.substring(0, i), 
45                                leftPart.substring(i), 
46                                rightPart.substring(0, j + 1), 
47                                rightPart.substring(j + 1));
48                }
49            }
50        }
51      
52        // Return the answer string with the minimum result after placing parentheses
53        return answer;
54    }
55}
56

1#include <string>
2#include <climits>
3#include <vector>
4
5// Function to convert a vector of char digits to an integer, or return 1 if the vector is empty
6int GetNum(const std::vector<char>& digits) {
7    if (digits.empty()) {
8        return 1;
9    }
10    return std::stoi(std::string(digits.begin(), digits.end()));
11}
12
13// Function to find the optimal insertion of parentheses in an addition expression to minimize result
14std::string MinimizeResult(const std::string& expression) {
15    // Find the position of the plus sign
16    size_t plusPosition = expression.find('+');
17    // Split the expression into two parts based on the plus sign
18    std::string leftPart = expression.substr(0, plusPosition);
19    std::string rightPart = expression.substr(plusPosition + 1);
20
21    // Initialize minimum sum to a very large number
22    int minimumSum = INT_MAX;
23    // String to hold the answer
24    std::string answer;
25
26    // Vectors to hold the digits of the current partition
27    std::vector<char> prefixArray, currentLeftArray(leftPart.begin(), leftPart.end()), 
28                      currentRightArray(rightPart.begin(), rightPart.end()), suffixArray;
29
30    // Iterate through the left part of the equation character by character
31    for (size_t i = 0; i <= leftPart.size(); ++i) {
32        // Reset the current right array and suffix array for each iteration of the left array
33        currentRightArray.assign(rightPart.begin(), rightPart.end());
34        suffixArray.clear();
35
36        // Iterate through the right part of the equation character by character
37        for (size_t j = 0; j <= rightPart.size(); ++j) {
38            // Calculate the current value with the parentheses inserted
39            int currentValue = (GetNum(currentLeftArray) + GetNum(currentRightArray)) * 
40                               GetNum(prefixArray) * GetNum(suffixArray);
41            // If the current value is less than the minimum sum found so far
42            if (currentValue < minimumSum) {
43                // Update the minimum sum and the answer string
44                minimumSum = currentValue;
45                answer = std::string(prefixArray.begin(), prefixArray.end()) + 
46                         "(" + std::string(currentLeftArray.begin(), currentLeftArray.end()) + 
47                         "+" + std::string(currentRightArray.begin(), currentRightArray.end()) + 
48                         ")" + std::string(suffixArray.begin(), suffixArray.end());
49            }
50            // If there are still characters in the right array, relocate the last one to the suffix array
51            if (!currentRightArray.empty()) {
52                suffixArray.insert(suffixArray.begin(), currentRightArray.back());
53                currentRightArray.pop_back();
54            }
55        }
56        // If there are still characters in the left array, relocate the first one to the prefix array
57        if (!currentLeftArray.empty()) {
58            prefixArray.push_back(currentLeftArray.front());
59            currentLeftArray.erase(currentLeftArray.begin());
60        }
61    }
62
63    // Return the answer
64    return answer;
65}
66

1// Function to find the optimal insertion of parentheses in an addition expression to minimize result
2function minimizeResult(expression: string): string {
3    // Split the expression into two numbers based on the plus sign
4    const [leftPart, rightPart] = expression.split('+');
5    // Initialize minimum sum to a very large number
6    let minimumSum = Number.MAX_SAFE_INTEGER;
7    // String to hold the answer
8    let answer = '';
9    // Split the left and right parts of the equation into arrays
10    let prefixArray = [], currentLeftArray = leftPart.split(''), currentRightArray = rightPart.split(''), suffixArray = [];
11
12    // Iterate through the left part of the equation
13    while (currentLeftArray.length) {
14        // Reset the current right array and suffix array for each iteration of the left array
15        currentRightArray = rightPart.split('');
16        suffixArray = [];
17
18        // Iterate through the right part of the equation
19        while (currentRightArray.length) {
20            // Calculate the current value with the parentheses inserted
21            let currentValue = (getNum(currentLeftArray) + getNum(currentRightArray)) * getNum(prefixArray) * getNum(suffixArray);
22            // If the current value is less than the minimum sum found so far
23            if (currentValue < minimumSum) {
24                // Update the minimum sum and the answer string
25                minimumSum = currentValue;
26                answer = `${prefixArray.join('')}(${currentLeftArray.join('')}+${currentRightArray.join('')})${suffixArray.join('')}`;
27            }
28            // Move the last element from right to suffix for next iteration
29            suffixArray.unshift(currentRightArray.pop());
30        }
31        // Move the first element from left to prefix for next iteration
32        prefixArray.push(currentLeftArray.shift());
33    }
34
35    // Return the answer
36    return answer;
37}
38
39// Helper function to convert an array of string digits to a number, or return 1 if the array is empty
40function getNum(digitsArray: Array<string>): number {
41    return digitsArray.length ? Number(digitsArray.join('')) : 1;
42}
43

Time and Space Complexity

Time Complexity

The given code snippet involves a nested loop to check every possible way to insert parentheses into a mathematical expression to minimize its value. Here's a step-by-step analysis:

We are using two nested loops. The outer loop runs m times, and the inner loop runs n times, where m is the length of the string l before the "+" operator, and n is the length of the string r after the "+" operator.
Within the inner loop, the operations performed are constant time operations, which includes slicing of strings (which is O(k), where k is the slice length), integer conversion and arithmetic operations.
The string formatting inside the loop is also a constant time operation relative to the loop iterations, as it depends only on the lengths of the strings involved.

Given that the two loops are nested, the total time complexity is O(m * n * k), where k is the maximum slice length, which would be at most max(m, n) in this scenario.

Because slicing lengths vary with each loop iteration but are bounded by the lengths of l and r, the factor of k in the complexity can be subsumed under m and n, leading to a simplified time complexity of O(m * n).

Space Complexity

The space complexity of the code can be broken down as follows:

Constant space to store integers (mi for the minimum result, m and n for the lengths of l and r, a, b, c, and t for intermediate calculations).
Variable space for the string ans - since it stores strings of length proportional to the input expression, its space requirement will be O(m + n).
Additional space for the slices of the strings within the loop. These strings will also have their lengths bounded by m and n, however, this space is reused in each iteration and does not cumulatively add to the complexity.

Taking into account the largest factors, the overall space complexity is O(m + n). This includes the space needed to store the input and the space for the intermediate string formed while concatenating the result.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know