2232. Minimize Result by Adding Parentheses to Expression
Asked at Capital One
Difficulty
Medium
Time
O(L^2)
Space
O(L)
Pattern
String
Companies
1
Problem
You are given a string of the form "<num1>+<num2>", where both parts are positive integers written in decimal. For example, "247+38".
You must insert one pair of parentheses. The opening ( must go somewhere to the left of the +, and the closing ) must go somewhere to the right of the +. Digits that end up outside the parentheses are multiplied with the parenthesized sum, because in math a number written right next to a bracket means multiplication. So "2(47+38)" means 2 * (47 + 38).
Among all valid placements, return the expression string that evaluates to the smallest value. If several placements give the same smallest value, any one of them is accepted. The expression is very short (at most 10 characters), so you can simply try every placement.
One bracket pair, two cut points
Constraints
- ●
3 <= expression.length <= 10 - ●
expression consists only of digits '1' to '9' and exactly one '+' - ●
expression starts and ends with a digit - ●
The original value and every value reachable by a valid placement fit in a signed 32-bit integer
Examples
expression = "247+38""2(47+38)"expression = "12+34""1(2+3)4"expression = "999+999""(999+999)"Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Capital One | Medium | View all Capital One questions → |
How to Think About It
Split at + into left and right. The open parenthesis goes before some digit of left, and the close parenthesis goes after some digit of right.
For an open position i and close position j: a = left[:i] (multiplier, 1 if empty), b = left[i:], c = right[:j+1], d = right[j+1:] (multiplier, 1 if empty). The value is a * (b + c) * d.
Both sides have at most 9 digits, so there are at most 9 * 9 = 81 placements — brute force is the intended solution.
Track the minimum value and build the output string for it.
Walkthrough for "247+38": placing ( before 47 and ) after 38 gives 2 * (47 + 38) = 170, the minimum.
Optimal Approach
Step 1: left, right = expression.split("+").
Step 2: For i in 0..len(left)-1 and j in 0..len(right)-1:
a = int(left[:i]) or 1, b = int(left[i:]), c = int(right[:j+1]), d = int(right[j+1:]) or 1.
val = a * (b + c) * d; keep the best and its string left[:i] + "(" + left[i:] + "+" + right[:j+1] + ")" + right[j+1:].
Step 3: Return the best string.
Time: O(L²) placements with O(L) parsing each. Space: O(L).
Try every cut point
What Trips People Up in Real Interviews
Treating an empty prefix or suffix as 0 instead of 1. An empty multiplier means "no multiplication".
Allowing the parentheses to exclude every digit on one side — each side of the + must keep at least one digit inside.
Looking for a clever greedy. With at most 81 options, brute force is the right call — say so.
Integer overflow in C++/Java: products of up to 9-digit numbers need 64-bit arithmetic.
Solution Code
O(L^2) timedef minimizeResult(expression):
left, right = expression.split('+')
best_val = None
best = ''
for i in range(len(left)):
for j in range(len(right)):
a = int(left[:i]) if i > 0 else 1
b = int(left[i:])
c = int(right[:j + 1])
d = int(right[j + 1:]) if j + 1 < len(right) else 1
val = a * (b + c) * d
if best_val is None or val < best_val:
best_val = val
best = left[:i] + '(' + left[i:] + '+' + right[:j + 1] + ')' + right[j + 1:]
return bestFrequently Asked Questions
What is the Minimize Result by Adding Parentheses to Expression problem?
Minimize Result by Adding Parentheses to Expression gives you a string like `"247+38"` and asks where to place one pair of parentheses around the `+` so the value is as small as possible, where digits outside the parentheses multiply the parenthesized sum — `"2(47+38)"` means `2 * (47 + 38) = 170`. The expression is short, so enumerate every placement.
How do you solve Minimize Result by Adding Parentheses to Expression?
The optimal approach runs in O(L^2) time and O(L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimize Result by Adding Parentheses to Expression?
Minimize Result by Adding Parentheses to Expression is asked at Capital One. It is a medium difficulty problem.
What are common mistakes on Minimize Result by Adding Parentheses to Expression?
- Treating an empty prefix or suffix as 0 instead of 1. An empty multiplier means "no multiplication".
- Allowing the parentheses to exclude every digit on one side — each side of the `+` must keep at least one digit inside.
- Looking for a clever greedy. With at most 81 options, brute force is the right call — say so.
- Integer overflow in C++/Java: products of up to 9-digit numbers need 64-bit arithmetic.