Insert Addition and Multiplication Operators
Pinterest● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given an integer array numbers and an integer target. Insert exactly one binary operator, either + or *, between every pair of adjacent array elements.
Evaluate each resulting expression using ordinary arithmetic precedence, so every multiplication is performed before addition. Return every expression whose value equals target.
- Use every number exactly once and preserve the original order.
- Do not concatenate adjacent numbers.
- Write each number in its ordinary decimal form with no spaces around operators.
- Return distinct expressions in ascending lexicographic order.
Function
findExpressions(numbers: int[], target: long) → String[]Examples
Example 1
numbers = [1,2,3,4]target = 10return = ["1*2*3+4","1+2+3+4"]Under normal precedence, both 1 * 2 * 3 + 4 and 1 + 2 + 3 + 4 equal 10. No other placement of the permitted operators does.
Example 2
numbers = [2,3,2]target = 8return = ["2*3+2","2+3*2"]Multiplication is evaluated first, so both 2 * 3 + 2 and 2 + 3 * 2 equal 8.
Example 3
numbers = [0,5,0]target = 0return = ["0*5*0","0*5+0","0+5*0"]Zero-valued multiplication groups create three different valid expressions. The result is sorted lexicographically.
Constraints
2 <= numbers.length <= 15.0 <= numbers[i] <= 9.0 <= target <= 10^15.- Every complete expression value fits in a signed 64-bit integer under these bounds.