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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Result by Adding Parentheses to Expression

Number: 2328

Difficulty: Medium

Paid? No

Companies: Pinterest

Problem Description

Given a string expression of the form "num1+num2" (where num1 and num2 are positive integers), insert exactly one pair of parentheses into the expression such that the left parenthesis is inserted before the '+' sign and the right parenthesis is inserted after the '+' sign. This insertion must yield a mathematically valid expression that evaluates to the smallest possible value. The evaluation is performed as follows: any sequence of digits immediately adjacent to the parentheses (to its left or right) is treated as a multiplication factor for the value inside the parentheses. If there is no number on one side, that factor is considered 1.

Key Insights

  • The expression always contains exactly one '+'; the parentheses must enclose the '+'.
  • You can choose any valid insertion point for the left parenthesis (within the first number) and any valid insertion point for the right parenthesis (within the second number).
  • The overall evaluated result can be broken down as: (left multiplier) * (sum inside parentheses) * (right multiplier). If no digits exist on one side of the parentheses placement, treat that multiplier as 1.
  • Because the maximum length of the expression is small, a brute-force enumeration of all possible valid insertions is acceptable.
  • Iterate over all potential placements, calculate the resulting value, and track the minimal value and corresponding placement.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the expression (since there are at most O(n^2) possibilities to check) Space Complexity: O(1), aside from variables used for tracking the minimum value and answer

Solution

We can solve the problem by iterating over every possible insertion index for the left parenthesis in the first number (including before the first digit) and for the right parenthesis in the second number (including after the last digit). For each candidate, we:

  1. Identify the left multiplier (number formed by digits left of left parenthesis, or 1 if empty).
  2. Identify the inside sum (the part inside the parentheses, which is split by the '+' already present).
  3. Identify the right multiplier (number formed by the digits after the closing parentheses, or 1 if empty).
  4. Compute the result as left_multiplier * (num_inside1 + num_inside2) * right_multiplier.
  5. Track the candidate that yields the minimum result. Data structures used are simple variables and strings. The algorithm leverages brute-force enumeration, allowed by the input size constraints.

Code Solutions

# Python solution with line-by-line comments

def minimizeResult(expression: str) -> str:
    # Split the expression into two parts based on the '+' operator
    plus_index = expression.index('+')
    left_number = expression[:plus_index]
    right_number = expression[plus_index+1:]
    
    min_result = float('inf')
    best_expression = ""
    
    # Enumerate all possible positions for the left parenthesis in left_number.
    for i in range(len(left_number)):
        # Enumerate all possible positions for the right parenthesis in right_number.
        for j in range(1, len(right_number)+1):
            # Extract the parts outside and inside of the parentheses.
            left_multiplier_str = left_number[:i]  # potential multiplier on the left
            inside_left_str = left_number[i:]       # part of the first number inside the parenthesis
            inside_right_str = right_number[:j]      # part of the second number inside the parenthesis
            right_multiplier_str = right_number[j:]  # potential multiplier on the right
            
            # Convert empty strings to multiplier of 1, otherwise to integer.
            left_multiplier = int(left_multiplier_str) if left_multiplier_str != "" else 1
            inside_left = int(inside_left_str)
            inside_right = int(inside_right_str)
            right_multiplier = int(right_multiplier_str) if right_multiplier_str != "" else 1
            
            current_result = left_multiplier * (inside_left + inside_right) * right_multiplier
            
            # Update the best result and corresponding expression if a new minimum is found.
            if current_result < min_result:
                min_result = current_result
                # Build the final string: insert parentheses around the chosen parts.
                # left part outside parentheses + '(' + inside_left_str + '+' + inside_right_str + ')' + right_multiplier_str
                best_expression = left_multiplier_str + "(" + inside_left_str + "+" + inside_right_str + ")" + right_multiplier_str
            
    return best_expression

# Example usage
if __name__ == "__main__":
    expr = "247+38"
    print(minimizeResult(expr))  # Expected output: "2(47+38)" or any valid minimal form
← Back to All Questions