{x}
blog image

Minimize Result by Adding Parentheses to Expression

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

 

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

 

Constraints:

  • 3 <= expression.length <= 10
  • expression consists of digits from '1' to '9' and '+'.
  • expression starts and ends with digits.
  • expression contains exactly one '+'.
  • The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Solution Explanation

The problem asks to find the minimum result of an expression of the form <num1> + <num2> by adding parentheses. The parentheses must be placed around a part of <num1> and a part of <num2> such that the expression is valid and the result is minimized.

The solution uses a brute-force approach. It iterates through all possible positions for the opening and closing parentheses, calculates the resulting value, and keeps track of the minimum value and the corresponding expression.

Algorithm:

  1. Split the expression: Split the input string expression into two substrings num1 and num2 at the '+' sign.
  2. Iterate through positions: Use nested loops to iterate through all possible positions i for the opening parenthesis in num1 and j for the closing parenthesis in num2.
  3. Calculate the value: For each pair of (i, j), calculate the value of the expression using the following steps:
    • Extract the parts of num1 and num2 inside the parentheses: num1[i:] and num2[:j+1].
    • Calculate the sum of the parts inside the parentheses: c = int(num1[i:]) + int(num2[:j+1]).
    • Extract the parts of num1 and num2 outside the parentheses: num1[:i] and num2[j+1:]. If a part is empty, treat it as 1. Otherwise, convert it to an integer.
    • Calculate the final result: t = a * b * c.
  4. Update minimum: If the calculated value t is less than the current minimum mi, update mi to t and store the corresponding expression in ans.
  5. Return the result: After iterating through all positions, return the expression ans that corresponds to the minimum value mi.

Time Complexity Analysis:

The time complexity is O(m*n), where m is the length of num1 and n is the length of num2. The nested loops iterate through all possible combinations of parenthesis placements.

Space Complexity Analysis:

The space complexity is O(1) as the algorithm uses only a constant amount of extra space to store variables. The space used for the input string and the output string is not considered in the space complexity analysis.

Code Examples (Python, Java, TypeScript):

The provided code examples implement the algorithm described above. They differ slightly in syntax and library functions used, but the core logic remains the same. The Python and Java examples are more concise and efficient than the TypeScript example. The TypeScript example uses helper functions to handle string manipulation and number conversion.

Example Walkthrough (Python):

Let's trace the Python code for the input expression = "247+38":

The outer loop iterates from i = 0 to i = 2. The inner loop iterates from j = 0 to j = 1.

  • i = 0, j = 0: c = 47 + 38 = 85, a = 1, b = 1, t = 1 * 1 * 85 = 85. ans becomes (247+38).
  • i = 0, j = 1: c = 47 + 3 = 50, a = 1, b = 8, t = 1 * 8 * 50 = 400.
  • i = 1, j = 0: c = 47 + 38 = 85, a = 2, b = 1, t = 2 * 1 * 85 = 170. ans becomes 2(47+38).
  • i = 1, j = 1: c = 7 + 3 = 10, a = 2, b = 8, t = 2 * 8 * 10 = 160. ans becomes 2(7+3)8.
  • i = 2, j = 0: c = 7 + 38 = 45, a = 24, b = 1, t = 24 * 1 * 45 = 1080.
  • i = 2, j = 1: c = 7 + 3 = 10, a = 24, b = 8, t = 24 * 8 * 10 = 1920.

The minimum value is 160, and the corresponding expression is 2(7+3)8. Note that the provided code example might give a slightly different best expression. The exact choice depends on the order of evaluation of the loops. The important thing is that the optimal value is achieved.