Minimize Result by Adding Parentheses to Expression

Minimize Result by Adding Parentheses to Expression - Problem

String Enumeration Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: expression = "247+38"

› Output: "(247+38)"

💡 Note: We can place parentheses as: (247+38)=285, (247)+38=247*38=9386, 2(47+38)=2*85=170, 24(7+38)=24*45=1080. The minimum is 285.

Example 2 — Different Numbers

$ Input: expression = "12+34"

› Output: "(12+34)"

💡 Note: Possible placements: (12+34)=46, (12)+34=12*34=408, 1(2+34)=1*36=36. The minimum is 36, so we return "1(2+34)".

Example 3 — Single Digits

$ Input: expression = "2+3"

› Output: "(2+3)"

💡 Note: Only one valid placement: (2+3)=5. This is the minimum and only option.

Constraints

1 ≤ expression.length ≤ 10
expression consists of digits and exactly one '+'
All numbers in expression are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input

Expression "247+38" needs parentheses added

Process

Try all valid parentheses positions and evaluate

Output

Return expression with minimum evaluation result

Key Takeaway

🎯 Key Insight: Since we add multiplication by splitting the expression, keeping the full addition usually gives the minimum result

Asked in

G Google 15 M Microsoft 12

The key insight is that we need to try all valid parentheses placements since multiplication can make results smaller or larger unpredictably. Best approach is systematic enumeration with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Enumerate All Positions	O(n²)	O(1)	Try every valid position for left and right parentheses
Systematic Enumeration	O(n²)	O(1)	Same approach but with cleaner implementation and early optimization hints

Enumerate All Positions — Algorithm Steps

Step 1: Find the '+' sign position in the expression
Step 2: Try all positions for '(' from start to before '+'
Step 3: Try all positions for ')' from after '+' to end
Step 4: For each combination, evaluate the expression and track minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Plus

Locate the '+' sign in expression

Try Positions

Test all valid (left, right) parentheses positions

Track Minimum

Keep the expression that gives smallest value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int evaluateExpression(const char* expr) {
    int parenStart = strchr(expr, '(') - expr;
    int parenEnd = strchr(expr, ')') - expr;
    
    char leftPart[100], middlePart[100], rightPart[100];
    strncpy(leftPart, expr, parenStart);
    leftPart[parenStart] = '\0';
    
    int middleLen = parenEnd - parenStart - 1;
    strncpy(middlePart, expr + parenStart + 1, middleLen);
    middlePart[middleLen] = '\0';
    
    strcpy(rightPart, expr + parenEnd + 1);
    
    int leftVal = strlen(leftPart) == 0 ? 1 : atoi(leftPart);
    int rightVal = strlen(rightPart) == 0 ? 1 : atoi(rightPart);
    
    int parenVal;
    char* plusPos = strchr(middlePart, '+');
    if (plusPos != NULL) {
        *plusPos = '\0';
        parenVal = atoi(middlePart) + atoi(plusPos + 1);
    } else {
        parenVal = atoi(middlePart);
    }
    
    return leftVal * parenVal * rightVal;
}

char* solution(char* expression) {
    static char result[1000];
    char* plusPos = strchr(expression, '+');
    int plusIdx = plusPos - expression;
    int minVal = INT_MAX;
    
    for (int left = 0; left <= plusIdx; left++) {
        for (int right = plusIdx + 1; right <= strlen(expression); right++) {
            char newExpr[1000];
            strncpy(newExpr, expression, left);
            newExpr[left] = '\0';
            strcat(newExpr, "(");
            strncat(newExpr, expression + left, right - left);
            strcat(newExpr, ")");
            strcat(newExpr, expression + right);
            
            int val = evaluateExpression(newExpr);
            
            if (val < minVal) {
                minVal = val;
                strcpy(result, newExpr);
            }
        }
    }
    
    return result;
}

int main() {
    char expression[1000];
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = 0;
    
    char* result = solution(expression);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop for left parenthesis position (n positions), inner loop for right parenthesis position (n positions)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track minimum value and best expression

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

800 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Enumerate All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler