# 964. Least Operators to Express Number

Given a single positive integer `x`, we will 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 `/)`.  For example, with `x = 3`, we might write `3 * 3 / 3 + 3 - 3` which is a value of 3.

When writing such an expression, we adhere to the following conventions:

1. The division operator (`/`) returns rational numbers.
2. There are no parentheses placed anywhere.
3. We use the usual order of operations: multiplication and division happens before addition and subtraction.
4. It’s not allowed to use the unary negation operator (`-`).  For example, “`x - x`“ is a valid expression as it only uses subtraction, but “`-x + x`“ is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given `target`.  Return the least number of operators used.

Example 1:

``````Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.
``````

Example 2:

``````Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.
``````

Example 3:

``````Input: x = 100, target = 100000000
Output: 3
Explanation: 100 * 100 * 100 * 100.  The expression contains 3 operations.
``````

Note:

• `2 <= x <= 100`
• `1 <= target <= 2 * 10^8`

``````class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
if (x == target) return 0;
if (x > target) {
return min(target * 2 - 1, (x - target) * 2);
}
long sum = x;
int cnt = 0;
while (sum < target) {
sum *= x;
++cnt;
}
if (sum == target) return cnt;
int res1 = INT_MAX, res2 = INT_MAX;
if (sum - target < target) {
res1 = leastOpsExpressTarget(x, sum - target) + cnt;
}
res2 = leastOpsExpressTarget(x, target - (sum / x)) + cnt - 1;
return min(res1, res2) + 1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/964

https://leetcode.com/problems/least-operators-to-express-number/

https://leetcode.com/problems/least-operators-to-express-number/discuss/208445/c%2B%2B-recursive-easy-to-understand

https://leetcode.com/problems/least-operators-to-express-number/discuss/208349/JavaC%2B%2BPython-O(logY)-Time-and-O(1)-Space

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation