Leetcode 964. Least Operators to Express Number
This problem is about finding the least number of operators to express a number. This task can be achieved by Depth First Search(DFS) algorithm with the help of dynamic programming (DP).
Given a single positive integer x
, we need to write an expression such as:
x (op1) x (op2) x (op3) x ...
where each operator belong to { +, -, *, /} and the expression equals the given target
. We return the least number of operators used.
Understanding the problem with an example :
Let's take example where x = 3 and target = 19.
In this case, the expression that equals 19 with minimum operators is 3 * 3 + 3 * 3 + 3 / 3
. This expression has 5 operations. So, the output would be 5.
Approach of the Solution :
We will define a DFS function dfs
which adopt the dynamic programming (DP) approach. This function computes the minimum number of operations required to reach the target
from x
. As the number of operations can be large, we use memoization to save the result for each target
so we avoid redundant calculations.
In each call of dfs, we handle three cases :
- When
x
is greater thantarget
, we return the minimum of 2 *target
- 1 and 2 * (x
-target
). - When
x
is equal totarget
, we return 0. - When
x
<target
, we use a loop to increasex
until it exceedstarget
. Then we compare the minimum number of operations required to make thetarget
fromx
andx * x
.
In the end, we use the min()
function to determine the smaller one between the current result and the new updated target target - x
, and return the final answer.
C++ Solution :
1
2cpp
3class Solution {
4 public:
5 int leastOpsExpressTarget(int x, int target) {
6 return dfs(x, target, {});
7 }
8
9 private:
10 int dfs(int x, int target, unordered_map<int, int>&& memo) {
11 if (const auto it = memo.find(target); it != cend(memo))
12 return it->second;
13 if (x > target)
14 return min(2 * target - 1, 2 * (x - target));
15 if (x == target)
16 return 0;
17
18 long prod = x;
19 int n = 0;
20 while (prod < target) {
21 prod *= x;
22 ++n;
23 }
24 if (prod == target)
25 return memo[target] = n;
26
27 int ans = dfs(x, target - prod / x, move(memo)) + n;
28 if (prod < 2 * target)
29 ans = min(ans, dfs(x, prod - target, move(memo)) + n + 1);
30 return memo[target] = ans;
31 }
32};
Python, Java, JavaScript and C# solutions will be needed for the explanation. Unfortunately, I am only able to provide C++ solution for now.# Python Solution
Below is the solution in Python using Depth-First Search (DFS) and Dynamic Programming (DP).
1
2python
3class Solution:
4 def leastOpsExpressTarget(self, x: int, target: int) -> int:
5 dp = {}
6 def dfs(target):
7 if target in dp: return dp[target]
8 if target < x: return min(2*target - 1, 2*(x-target))
9 t, cost = x, 0
10 while t < target:
11 t *= x
12 cost += 1
13 if t == target: return cost
14 else:
15 ans = cost if t - target < target else float('inf')
16 dp[target] = min(ans + dfs(t - target), cost + 1 + dfs(target - t // x))
17 return dp[target]
18 return dfs(target)
JavaScript Solution:
In JavaScript, the solution is as follows:
1 2javascript 3var leastOpsExpressTarget = function(x, target) { 4 let memo = {} 5 function dfs(target) { 6 if (target in memo) return memo[target] 7 if (target < x) return Math.min(target * 2 - 1, (x - target) * 2) 8 let t = x, cost = 0 9 while (t < target) { 10 t *= x 11 cost ++ 12 } 13 if (t == target) return cost 14 memo[target] = cost + (t - target < target ? dfs(t - target) : Infinity) 15 if (t / x >= target) 16 memo[target] = Math.min(memo[target], cost - 1 + dfs(target - t / x)) 17 return memo[target] 18 } 19 return dfs(target) 20};
Java Solution:
And finally, the Java solution can be written as:
1
2java
3class Solution {
4 Map<Integer, Integer> memo;
5 int x;
6 public int leastOpsExpressTarget(int x, int target) {
7 this.x = x;
8 memo = new HashMap<>();
9 return dp(target) - 1;
10 }
11
12 public int dp(int target) {
13 if (target == 0) return 0;
14 if (target < x) return Math.min(2 * target - 1, 2 * (x - target));
15 if (memo.containsKey(target)) return memo.get(target);
16
17 long t = x;
18 int cost = 0;
19 while (t < target) {
20 t *= x;
21 cost ++;
22 }
23 int ans;
24 if (t == target) {
25 ans = cost;
26 } else {
27 ans = Math.min(
28 (int)Math.pow(x, cost) + dp((int)(t - target)),
29 t / x < target ? Integer.MAX_VALUE: cost + dp((int)(target - t / x))
30 );
31 }
32 memo.put(target, ans);
33 return ans;
34 }
35}
Each language solution uses Depth-First Search (DFS) and Dynamic Programming (DP) as described above to solve the given problem. Importantly, note how each solution uses hash map (Python), javascript object (JavaScript), and a map (Java) to implement memoization and avoid repeated computations.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.