Problem Description

You are given a string expression in the format "<num1>+<num2>" where <num1> and <num2> are positive integers.

Your task is to add exactly one pair of parentheses to the expression such that:

• The left parenthesis ( must be placed somewhere to the left of the + sign
• The right parenthesis ) must be placed somewhere to the right of the + sign
• After adding the parentheses, the expression remains mathematically valid
• The resulting expression evaluates to the smallest possible value

For example, if the expression is "247+38", you could place parentheses in various ways:

• "2(47+3)8" evaluates to 2 * (47 + 3) * 8 = 2 * 50 * 8 = 800
• "2(47+38)" evaluates to 2 * (47 + 38) = 2 * 85 = 170
• "(247+3)8" evaluates to (247 + 3) * 8 = 250 * 8 = 2000
• "24(7+38)" evaluates to 24 * (7 + 38) = 24 * 45 = 1080

The goal is to find the placement that gives the minimum result. In this case, "2(47+38)" with a value of 170 would be the answer.

Note that:

• Numbers outside the parentheses are multiplied with the sum inside the parentheses
• If there's no number before the left parenthesis, it's treated as multiplication by 1
• If there's no number after the right parenthesis, it's treated as multiplication by 1

Return the expression string with the parentheses added that produces the minimum value. If multiple placements yield the same minimum value, return any valid one.

Intuition

When we place parentheses in the expression, we're essentially deciding how to split the two numbers and what operations to perform. Let's think about what happens when we place parentheses at different positions.

Given an expression like "247+38", when we place parentheses like "24(7+38)", we're actually creating three parts:

• The part before the left parenthesis: "24"
• The part inside the parentheses: "7+38"
• The part after the right parenthesis: "" (empty in this case)

The key insight is that the final value is calculated as: before × (inside_sum) × after

So for "24(7+38)", it becomes: 24 × (7 + 38) × 1 = 24 × 45 = 1080

To minimize the result, we need to consider all possible ways to split the original numbers. For the left number <num1>, we can split it at any position (or not split at all). Similarly, for the right number <num2>, we can split it at any position.

The brute force approach becomes clear: try all possible positions for the left parenthesis (which determines how we split <num1>) and all possible positions for the right parenthesis (which determines how we split <num2>). For each combination:

1. Extract the part of <num1> that goes inside the parentheses
2. Extract the part of <num2> that goes inside the parentheses
3. Calculate the sum inside the parentheses
4. Multiply by the parts outside (treating empty parts as 1)
5. Keep track of the minimum value and its corresponding parenthesis placement

Since we're trying all possible combinations and the numbers are guaranteed to fit in a 32-bit integer, this exhaustive search will find the optimal solution.

Solution Approach

The implementation follows a nested loop approach to try all possible parenthesis placements:

1. Split the expression: First, we split the original expression by the "+" sign to get the left number l and right number r. We also store their lengths as m and n.

2. Initialize tracking variables: We use mi to track the minimum value found (initialized to infinity) and ans to store the corresponding expression string.

3. Try all possible splits: We use two nested loops:

   • Outer loop with index i from 0 to m-1: determines where to place the left parenthesis in the left number
   • Inner loop with index j from 0 to n-1: determines where to place the right parenthesis in the right number

4. For each combination (i, j), we extract three components:

   • c = int(l[i:]) + int(r[:j+1]): The sum inside the parentheses
     • l[i:] is the part of the left number inside parentheses
     • r[:j+1] is the part of the right number inside parentheses
   • a: The multiplier before the parentheses
     • If i == 0, there's nothing before, so a = 1
     • Otherwise, a = int(l[:i])
   • b: The multiplier after the parentheses
     • If j == n-1, there's nothing after, so b = 1
     • Otherwise, b = int(r[j+1:])

5. Calculate the result: The total value is t = a * b * c

6. Update minimum: If this value t is less than our current minimum mi, we update both mi and construct the answer string using string formatting:

   ans = f"{l[:i]}({l[i:]}+{r[:j+1]}){r[j+1:]}"

   This places the parentheses at the correct positions in the original expression.

7. Return the result: After trying all combinations, return the ans string that corresponds to the minimum value.

The time complexity is O(m * n) where m and n are the lengths of the two numbers, as we try all possible split positions. The space complexity is O(1) aside from the output string.

Example Walkthrough

Let's walk through the solution with the example "12+34".

Step 1: Split the expression

• Split by "+": l = "12", r = "34"
• Lengths: m = 2, n = 2

Step 2: Initialize tracking

• mi = infinity
• ans = ""

Step 3: Try all possible parenthesis placements

We'll iterate through all combinations of (i, j):

When i = 0, j = 0:

• Inside parentheses: l[0:] + r[:1] = "12" + "3" = 12 + 3 = 15
• Before parentheses: l[:0] = "" → a = 1
• After parentheses: r[1:] = "4" → b = 4
• Result: t = 1 × 15 × 4 = 60
• Expression: "(12+3)4"
• Update: mi = 60, ans = "(12+3)4"

When i = 0, j = 1:

• Inside parentheses: l[0:] + r[:2] = "12" + "34" = 12 + 34 = 46
• Before parentheses: l[:0] = "" → a = 1
• After parentheses: r[2:] = "" → b = 1
• Result: t = 1 × 46 × 1 = 46
• Expression: "(12+34)"
• Update: mi = 46, ans = "(12+34)"

When i = 1, j = 0:

• Inside parentheses: l[1:] + r[:1] = "2" + "3" = 2 + 3 = 5
• Before parentheses: l[:1] = "1" → a = 1
• After parentheses: r[1:] = "4" → b = 4
• Result: t = 1 × 5 × 4 = 20
• Expression: "1(2+3)4"
• Update: mi = 20, ans = "1(2+3)4"

When i = 1, j = 1:

• Inside parentheses: l[1:] + r[:2] = "2" + "34" = 2 + 34 = 36
• Before parentheses: l[:1] = "1" → a = 1
• After parentheses: r[2:] = "" → b = 1
• Result: t = 1 × 36 × 1 = 36
• Expression: "1(2+34)"
• No update since 36 > 20

Step 4: Return result The minimum value is 20, achieved with the expression "1(2+3)4".

This demonstrates how the algorithm systematically checks all possible ways to place parentheses and finds the placement that yields the smallest result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the length of the left operand and n is the length of the right operand in the expression.

The algorithm uses two nested loops:

• The outer loop iterates through all possible positions i in the left operand (from 0 to m-1)
• The inner loop iterates through all possible positions j in the right operand (from 0 to n-1)

For each combination of (i, j), the operations performed are:

• String slicing operations: l[i:], r[:j+1], l[:i], r[j+1:] - each takes O(1) to O(m) or O(n) time
• Integer conversions: int() operations - O(k) where k is the length of the substring
• Arithmetic operations and comparisons - O(1)
• String formatting - O(m + n)

Since string operations are bounded by the length of the operands and we perform them a constant number of times per iteration, the dominant factor is the nested loops, giving us O(m * n).

Space Complexity: O(m + n)

The space usage includes:

• Variables l and r to store the split operands - O(m + n)
• Temporary strings created during slicing operations - O(m + n) in the worst case
• Variable ans to store the result string - O(m + n)
• Other scalar variables (i, j, a, b, c, mi, t) - O(1)

The space complexity is dominated by the string storage, resulting in O(m + n).

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

Common Pitfalls

1. Empty String Multiplication

One of the most common pitfalls is not handling empty strings correctly when extracting multipliers. When the parenthesis is placed at the beginning or end of the expression, the substring extraction might result in an empty string, which cannot be converted to an integer.

Problem Example:

# If left_paren_pos = 0, then left_operand[:0] = ""
# int("") will throw a ValueError
left_multiplier = int(left_operand[:left_paren_pos])  # Error!

Solution: Always check if the substring is empty before converting to integer, or use conditional logic:

left_multiplier = 1 if left_paren_pos == 0 else int(left_operand[:left_paren_pos])
right_multiplier = 1 if right_paren_pos == right_length - 1 else int(right_operand[right_paren_pos + 1:])

2. Incorrect Index Boundaries

Another pitfall is using incorrect indices for string slicing, especially for the right parenthesis position. The confusion often arises from whether to use right_paren_pos or right_paren_pos + 1.

Problem Example:

# Incorrect: missing the digit at right_paren_pos
inside_sum = int(left_operand[left_paren_pos:]) + int(right_operand[:right_paren_pos])

Solution: Remember that Python slicing is exclusive of the end index, so use right_paren_pos + 1:

inside_sum = int(left_operand[left_paren_pos:]) + int(right_operand[:right_paren_pos + 1])

3. Off-by-One Errors in Loop Ranges

Using incorrect loop ranges can cause you to miss valid parenthesis placements or attempt invalid ones.

Problem Example:

# This misses the case where all digits are inside parentheses
for left_paren_pos in range(1, left_length):  # Starts from 1 instead of 0
    for right_paren_pos in range(right_length - 1):  # Excludes last position

Solution: Ensure loops cover all valid positions:

for left_paren_pos in range(left_length):  # 0 to left_length-1
    for right_paren_pos in range(right_length):  # 0 to right_length-1

4. String Construction Errors

When building the result string, it's easy to misplace parts of the original expression or forget to include all components.

Problem Example:

# Forgetting parts of the expression or using wrong indices
result = f"({left_operand[left_paren_pos:]}+{right_operand[:right_paren_pos + 1]})"
# Missing: left_operand[:left_paren_pos] at the beginning and right_operand[right_paren_pos + 1:] at the end

Solution: Carefully construct the string with all four parts:

result = f"{left_operand[:left_paren_pos]}({left_operand[left_paren_pos:]}+{right_operand[:right_paren_pos + 1]}){right_operand[right_paren_pos + 1:]}"

The four parts are:

1. Numbers before the left parenthesis
2. Opening parenthesis and numbers from left operand inside
3. Plus sign and numbers from right operand inside with closing parenthesis
4. Numbers after the right parenthesis