Ctrl K

Brackets for the Smallest Value

Medium
You are given a string expr of the form A+B, where A and B are positive numbers whose digits are never zero. Insert exactly one pair of brackets into it: ( somewhere left of the + sign and ) somewhere right of it, so the result is a well-formed expression. A number placed right next to a bracket on the outside multiplies the bracketed value: 2(3+4)5 means 2 · (3 + 4) · 5 = 70. Return the bracketed string with the smallest value. If several strings tie, pick the one whose ( is furthest left, and among those the one whose ) is furthest left.
Example 1
expr='23+45' → '(23+45)'

The options are (23+45) = 68, (23+4)5 = 135, 2(3+45) = 96 and 2(3+4)5 = 70. The smallest is 68.

Example 2
expr='99+11' → '9(9+1)1'

9(9+1)1 = 9 · 10 · 1 = 90, while (99+11) = 110. The answer is "9(9+1)1".

Example 3
expr='7+8' → '(7+8)'
Constraints
  • 3 ≤ len(expr) ≤ 10
  • expr has the form A+B, where A and B are non-empty strings of digits 1–9
  • The value fits in a signed 32-bit integer
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsNext Time From the Same Digits MediumRestore the Lost Point MediumLatest Clock From Digits MediumSmallest Lock Code MediumSubstring Pairs With One Typo Medium
loading Python…
Input
expr='23+45'
Expected
'(23+45)'

Run checks the first 3 tests in your browser. Submit checks all 108 tests on the server, hidden ones included.