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 :

1. When x is greater than target, we return the minimum of 2 * target - 1 and 2 * (x - target).
2. When x is equal to target, we return 0.
3. When x < target, we use a loop to increase x until it exceeds target. Then we compare the minimum number of operations required to make the target from x and x * 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.