Minimize Result by Adding Parentheses to Expression
Minimize Result by Adding Parentheses to Expression is a medium arrays & hashing problem solved with the candidate generation pattern.
The best approach, optimal (enumerate split points directly), runs in O(n²) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (build every string and evaluate it) up.
Problem
You are given a string expression of the form "<num1>+<num2>", where both numbers are positive integers.
Insert exactly one '(' and one ')' so that the result is still a valid expression: the '(' must be placed somewhere to the left of the '+' (possibly before the first digit) and the ')' somewhere to the right of it (possibly after the last digit). A number written directly next to a parenthesis is multiplied with the parenthesised group, so "3(4+5)6" means 3 * (4 + 5) * 6.
Return the expression with parentheses that has the smallest possible value. If several placements share that value, any of them is accepted.
Examples
Example 1
- Input
expression = "12+34"- Output
"1(2+3)4"- Why
- This reads 1 * (2 + 3) * 4 = 20. The other placements give 46, 60 and 36.
Example 2
- Input
expression = "5+7"- Output
"(5+7)"- Why
- Each side has one digit, so the parentheses can only wrap the whole expression.
Example 3
- Input
expression = "999+1"- Output
"9(99+1)"- Why
- 9 * (99 + 1) = 900, smaller than (999+1) = 1000 and 99 * (9 + 1) = 990.
Constraints
3 <= expression.length <= 10expressionhas the form"<num1>+<num2>", where both numbers use digits 1–9 only.- The original expression and every possible placement evaluate to values that fit in a 32-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (build every string and evaluate it) | O(n³) | O(n) |
| Optimal (enumerate split points directly) | O(n²) | O(n) |
1Brute force (build every string and evaluate it)
O(n³)O(n²) placements, each building and scanning an O(n) string.O(n)One candidate string at a time.Generate each candidate string with parentheses inserted, then evaluate it with a small parser that reads numbers and treats a number touching a parenthesis as a multiplication. Keep the candidate with the smallest value.
- Let p be the index of '+'. For each i in 0..p-1 and each j in p+2..n, build
s[0..i) + "(" + s[i..j) + ")" + s[j..n). - Evaluate it: read the number before '(' (default 1), the two numbers inside, and the number after ')' (default 1).
- Value = before * (left + right) * after; keep the candidate if it is strictly smaller than the best so far.
class Solution {
public String minimizeResult(String expression) {
int n = expression.length(), p = expression.indexOf('+');
String best = "";
long bestVal = Long.MAX_VALUE;
for (int i = 0; i < p; i++)
for (int j = p + 2; j <= n; j++) {
String cand = expression.substring(0, i) + "(" + expression.substring(i, j) + ")" + expression.substring(j);
long v = eval(cand);
if (v < bestVal) {
bestVal = v;
best = cand;
}
}
return best;
}
private long eval(String s) {
long[] nums = new long[4];
nums[0] = 1;
nums[3] = 1;
int part = 0;
long cur = 0;
boolean has = false;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
cur = cur * 10 + (c - '0');
has = true;
} else {
if (has) nums[part] = cur;
cur = 0;
has = false;
part++;
}
}
if (has) nums[part] = cur;
return nums[0] * (nums[1] + nums[2]) * nums[3];
}
}class Solution:
def minimizeResult(self, expression: str) -> str:
def evaluate(s: str) -> int:
nums = [1, 0, 0, 1]
part, cur, has = 0, 0, False
for c in s:
if c.isdigit():
cur = cur * 10 + int(c)
has = True
else:
if has:
nums[part] = cur
cur, has = 0, False
part += 1
if has:
nums[part] = cur
return nums[0] * (nums[1] + nums[2]) * nums[3]
n, p = len(expression), expression.index('+')
best, best_val = "", None
for i in range(p):
for j in range(p + 2, n + 1):
cand = expression[:i] + "(" + expression[i:j] + ")" + expression[j:]
v = evaluate(cand)
if best_val is None or v < best_val:
best_val, best = v, cand
return bestclass Solution {
public:
string minimizeResult(string expression) {
int n = expression.size(), p = expression.find('+');
string best;
long long bestVal = LLONG_MAX;
for (int i = 0; i < p; i++)
for (int j = p + 2; j <= n; j++) {
string cand = expression.substr(0, i) + "(" + expression.substr(i, j - i) + ")" + expression.substr(j);
long long v = eval(cand);
if (v < bestVal) {
bestVal = v;
best = cand;
}
}
return best;
}
private:
long long eval(const string& s) {
long long nums[4] = {1, 0, 0, 1};
int part = 0;
long long cur = 0;
bool has = false;
for (char c : s) {
if (isdigit(c)) {
cur = cur * 10 + (c - '0');
has = true;
} else {
if (has) nums[part] = cur;
cur = 0;
has = false;
part++;
}
}
if (has) nums[part] = cur;
return nums[0] * (nums[1] + nums[2]) * nums[3];
}
};function minimizeResult(expression) {
const evaluate = (s) => {
const nums = [1, 0, 0, 1];
let part = 0, cur = 0, has = false;
for (const c of s) {
if (c >= '0' && c <= '9') {
cur = cur * 10 + (c.charCodeAt(0) - 48);
has = true;
} else {
if (has) nums[part] = cur;
cur = 0;
has = false;
part++;
}
}
if (has) nums[part] = cur;
return nums[0] * (nums[1] + nums[2]) * nums[3];
};
const n = expression.length, p = expression.indexOf('+');
let best = "", bestVal = Infinity;
for (let i = 0; i < p; i++)
for (let j = p + 2; j <= n; j++) {
const cand = expression.substring(0, i) + "(" + expression.substring(i, j) + ")" + expression.substring(j);
const v = evaluate(cand);
if (v < bestVal) {
bestVal = v;
best = cand;
}
}
return best;
}2Optimal (enumerate split points directly)
O(n²)O(n²) split pairs; with at most 10 characters each parse is effectively constant.O(n)Substrings and the final answer.Split the two numbers instead of building strings. For a '(' before index i of the left number and a ')' after index j of the right number, the value is prefix * (leftInner + rightInner) * suffix, with an empty prefix or suffix counting as 1. Compute the four parts from substrings, track the minimum, and build only the winning string at the end.
- Let
a = expression[0..p)andb = expression[p+1..n). - For i in 0..len(a)-1 and j in 1..len(b):
pre = i == 0 ? 1 : a[0..i),x = a[i..),y = b[0..j),suf = j == len(b) ? 1 : b[j..). - Value = pre * (x + y) * suf; remember (i, j) when it is strictly smaller.
- Return
a[0..i) + "(" + a[i..) + "+" + b[0..j) + ")" + b[j..)for the best pair.
class Solution {
public String minimizeResult(String expression) {
int p = expression.indexOf('+');
String a = expression.substring(0, p), b = expression.substring(p + 1);
long best = Long.MAX_VALUE;
int bi = 0, bj = b.length();
for (int i = 0; i < a.length(); i++)
for (int j = 1; j <= b.length(); j++) {
long pre = i == 0 ? 1 : Long.parseLong(a.substring(0, i));
long x = Long.parseLong(a.substring(i));
long y = Long.parseLong(b.substring(0, j));
long suf = j == b.length() ? 1 : Long.parseLong(b.substring(j));
long v = pre * (x + y) * suf;
if (v < best) {
best = v;
bi = i;
bj = j;
}
}
return a.substring(0, bi) + "(" + a.substring(bi) + "+" + b.substring(0, bj) + ")" + b.substring(bj);
}
}class Solution:
def minimizeResult(self, expression: str) -> str:
p = expression.index('+')
a, b = expression[:p], expression[p + 1:]
best, bi, bj = None, 0, len(b)
for i in range(len(a)):
for j in range(1, len(b) + 1):
pre = int(a[:i]) if i > 0 else 1
x = int(a[i:])
y = int(b[:j])
suf = int(b[j:]) if j < len(b) else 1
v = pre * (x + y) * suf
if best is None or v < best:
best, bi, bj = v, i, j
return a[:bi] + "(" + a[bi:] + "+" + b[:bj] + ")" + b[bj:]class Solution {
public:
string minimizeResult(string expression) {
int p = expression.find('+');
string a = expression.substr(0, p), b = expression.substr(p + 1);
long long best = LLONG_MAX;
int bi = 0, bj = b.size();
for (int i = 0; i < (int)a.size(); i++)
for (int j = 1; j <= (int)b.size(); j++) {
long long pre = i == 0 ? 1 : stoll(a.substr(0, i));
long long x = stoll(a.substr(i));
long long y = stoll(b.substr(0, j));
long long suf = j == (int)b.size() ? 1 : stoll(b.substr(j));
long long v = pre * (x + y) * suf;
if (v < best) {
best = v;
bi = i;
bj = j;
}
}
return a.substr(0, bi) + "(" + a.substr(bi) + "+" + b.substr(0, bj) + ")" + b.substr(bj);
}
};function minimizeResult(expression) {
const p = expression.indexOf('+');
const a = expression.substring(0, p), b = expression.substring(p + 1);
let best = Infinity, bi = 0, bj = b.length;
for (let i = 0; i < a.length; i++)
for (let j = 1; j <= b.length; j++) {
const pre = i === 0 ? 1 : parseInt(a.substring(0, i), 10);
const x = parseInt(a.substring(i), 10);
const y = parseInt(b.substring(0, j), 10);
const suf = j === b.length ? 1 : parseInt(b.substring(j), 10);
const v = pre * (x + y) * suf;
if (v < best) {
best = v;
bi = i;
bj = j;
}
}
return a.substring(0, bi) + "(" + a.substring(bi) + "+" + b.substring(0, bj) + ")" + b.substring(bj);
}Edge cases to test
- Single-digit numbers on both sides (only one placement)
- Wrapping the whole expression is the best choice
- Several placements tie for the minimum (any of them is accepted)
Hints
Hint 1
The '(' goes somewhere in the left number and the ')' goes somewhere in the right number. How many pairs of positions is that?
Hint 2
For a placement, the left number splits into a prefix multiplier and the part inside the parentheses; the right number splits into the part inside and a suffix multiplier. An empty multiplier counts as 1.
FAQ
What is the best time complexity for Minimize Result by Adding Parentheses to Expression?
Optimal (enumerate split points directly) runs in O(n²) time and O(n) extra space. O(n²) split pairs; with at most 10 characters each parse is effectively constant.
Which pattern does Minimize Result by Adding Parentheses to Expression use?
It is a arrays & hashing problem that uses the candidate generation pattern. Other problems with the same pattern: Find the Closest Palindrome.
Is there a brute force solution for Minimize Result by Adding Parentheses to Expression?
Yes. Brute force (build every string and evaluate it) takes O(n³) time and O(n) space. Generate each candidate string with parentheses inserted, then evaluate it with a small parser that reads numbers and treats a number touching a parenthesis as a multiplication.
Which edge cases should I test for Minimize Result by Adding Parentheses to Expression?
Single-digit numbers on both sides (only one placement); Wrapping the whole expression is the best choice; Several placements tie for the minimum (any of them is accepted).