Least Operators to Express Number
Given a single positive integer x, write an expression of the form x (op1) x (op2) x (op3) x ..., where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, *, or /).
When writing such an expression, follow these conventions:
- The division operator (
/) returns rational numbers. - There are no parentheses placed anywhere.
- Use the usual order of operations: multiplication and division happen before addition and subtraction.
- It is not allowed to use the unary negation operator (
-). For example,x - xis a valid expression because it only uses subtraction, but-x + xis not because it uses negation.
Return the least number of operators used such that the expression equals the given target.
Example 1
Input
x = 3, target = 19Output
5The expression
3 * 3 + 3 * 3 + 3 / 3 equals 19 and contains 5 operations.Example 2
Input
x = 5, target = 501Output
8The expression
5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5 equals 501 and contains 8 operations.Constraints
- 2 <= x <= 100
- 1 <= target <= 2 * 10^8