We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Result by Adding Parentheses to Expression

Difficulty: Medium

Problem Description

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.

Key Insights

  • The expression is in the form of two positive integers separated by a +.
  • To minimize the result, we can manipulate the integers by adding parentheses in different valid configurations.
  • The left integer can be divided into two parts where the first part is multiplied by the sum of the second part and the second integer.
  • We need to evaluate all possible pairs of digits from the left integer and the right integer to find the minimum value.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the expression. Space Complexity: O(1), since we are using a constant amount of space for variables.

Solution

To solve the problem, we can iterate through each possible split of the left integer and the right integer around the + sign. For each split, we compute the value of the expression formed by placing parentheses around the + sign. We keep track of the minimum value encountered and the corresponding expression that produces this minimum value. The final expression is returned as the output.

Code Solutions

def minimize_result(expression: str) -> str:
    num1, num2 = expression.split('+')
    min_value = float('inf')
    best_expression = expression

    # Iterate over possible splits of num1
    for i in range(len(num1)):
        left_part = num1[:i] if i > 0 else ''
        right_part = num1[i:]
        
        # Iterate over possible splits of num2
        for j in range(len(num2) + 1):
            left_num2 = num2[:j]
            right_num2 = num2[j:] if j < len(num2) else ''
            
            # Evaluate the expression with parentheses
            current_value = (int(left_part) if left_part else 1) * (int(right_part) + int(left_num2) if left_num2 else 0) + (int(right_num2) if right_num2 else 0)
            current_expression = f"{left_part}({right_part}+{left_num2}){right_num2}"

            # Update minimum value and expression
            if current_value < min_value:
                min_value = current_value
                best_expression = current_expression

    return best_expression
← Back to All Questions