# Least Operators to Express Number **Difficulty:** HARD [External](https://leetcode.com/problems/least-operators-to-express-number) Canonical: https://scaleengineer.com/dsa/problems/least-operators-to-express-number **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization) **Companies:** [Snap](https://scaleengineer.com/companies/snap) --- ## Problem 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: * The division operator (`/`) returns rational numbers. * There are no parentheses placed anywhere. * We 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 - 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. **Constraints:** * `2 <= x <= 100` * `1 <= target <= 2 * 108` # Approaches ## Brute-Force Recursion This approach attempts to solve the problem by exploring all possible sequences of operations in a depth-first manner. We start with an initial value (e.g., `x`) and recursively try to apply all valid operations (`+`, `-`, `*`, `/` which form terms `x^p`) until we reach the `target` value. The goal is to find the path of operations with the minimum length. **Time:** O(c^T) without memoization, where c is the branching factor and T is the target. With memoization, it's still very high due to the large state space. · **Space:** O(T) for the memoization table, where T is the target value. In the worst case, the recursion depth can also be large, contributing to stack space. **Pros:** Simple to conceptualize as a direct translation of the problem statement. **Cons:** Extremely high time complexity, as it explores many redundant and non-optimal paths.; The depth of the recursion can be very large, potentially leading to a stack overflow error without proper pruning.; Even with memoization, the number of states to visit can be enormous, making it impractical for the given constraints. ### Explanation The brute-force recursive approach explores every possible expression that can be formed. We can define a recursive function that tries to reach the `target` from the current value. At each step, we can add or subtract a term. A term is a power of `x`, like `x^p`, which is formed by `p-1` multiplications. The cost of adding such a term is `p` operators in total (1 for the `+` and `p-1` for the `*`s). Similarly, for `x/x=1`, the cost is 2 operators. This method will explore a vast tree of possibilities. Without memoization, it will recompute solutions for the same intermediate values multiple times, leading to an exponential time complexity. Even with memoization, the state space is too large to be practical, as we might need to compute the minimum operators for many values between 0 and `target` (and even beyond). ```java import java.util.HashMap; import java.util.Map; class Solution { Map memo; int x_val; public int leastOpsExpressTarget(int x, int target) { this.memo = new HashMap<>(); this.x_val = x; // We start from x, so we need one less operator than the number of x's used. // The cost of x itself is 0 operators. // The problem can be rephrased as finding min ops to get target from 0, // where the first term x^k costs k-1 ops, and subsequent terms cost k ops. // This is complex. A simpler model is to find min ops to get target from x. return solve(target); } private int solve(int currentTarget) { if (currentTarget == 0) return -1; // Should not happen if we start from x if (currentTarget == x_val) return 0; if (memo.containsKey(currentTarget)) return memo.get(currentTarget); long power = x_val; int p = 1; int minOps = Integer.MAX_VALUE; // Case 1: target = x * ... * x + ... // We try to reach target from a smaller value by multiplication if (currentTarget > x_val && currentTarget % x_val == 0) { minOps = Math.min(minOps, solve(currentTarget / x_val) + 1); } // Case 2: target = x + ... + x if (currentTarget > x_val && currentTarget % x_val != 0) { // Simplified heuristic minOps = Math.min(minOps, solve(currentTarget - x_val) + 1); } // This is a highly simplified and incorrect recursive solution to illustrate the idea. // A full brute-force would be much more complex. memo.put(currentTarget, minOps); return minOps; } } ``` *Note: The provided code is a conceptual illustration and not a complete or correct brute-force solution, which would be significantly more complex.* ### Algorithm 1. Define a recursive function, say `findMinOperators(currentValue)`, which calculates the minimum operators to reach `target` from `currentValue`. 2. The base cases for the recursion would be: - If `currentValue == target`, we have reached the destination, so we need 0 more operators. Return 0. - If `currentValue` exceeds `target` by a large margin or goes far below zero, it's likely not an optimal path. We can return infinity to prune this path. 3. In the recursive step, from `currentValue`, we can perform all possible operations. This means we can add or subtract any power of `x`. - For each power `p` of `x` (i.e., `x^1, x^2, ...`) and `x/x=1`: - Recursively call `findMinOperators(currentValue + x^p)` and `findMinOperators(currentValue - x^p)`. - The cost of adding/subtracting a term `x^p` is `p` operators (`p-1` for multiplication and `1` for `+` or `-`). For `x/x`, the cost is 2 operators (`/` and `+` or `-`). 4. The function returns the minimum cost among all possible next steps. 5. To avoid recomputing results for the same `currentValue`, memoization (a hash map) can be used to store the results. ## Dijkstra's Algorithm on States A more structured and efficient way to solve this problem is to treat it as a shortest path problem on an implicit graph. The nodes are the numbers we can form, and the edges represent the operations that transform one number to another. The weight of each edge is the number of operators required for that operation. Dijkstra's algorithm is perfectly suited for finding the minimum cost (least operators) to reach the `target` node. **Time:** O(E log V), where V is the number of states visited and E is the number of transitions. E is roughly `V * log_x(target)`. The performance depends heavily on how many states need to be explored to reach the target. · **Space:** O(V), where V is the number of states (values) visited. In the worst case, V can be proportional to `target`. **Pros:** Guaranteed to find the optimal solution because it explores paths in increasing order of cost.; More efficient than brute-force recursion by avoiding re-computation of states using the `dist` map. **Cons:** The number of states (values) can be large, potentially up to `2 * target`, which might lead to high memory usage for the `dist` map.; The time complexity can be high if the `target` is large and the optimal path involves many intermediate steps. ### Explanation We can think of the problem as finding the shortest path from 0 to `target`. The states in our search are the numbers we can generate. We use Dijkstra's algorithm to explore these states, always expanding the one that was reached with the fewest operators so far. A priority queue will store tuples of `(cost, value)`. We also use a map to store the minimum cost found so far for each value to avoid redundant processing. We start at `0` with a cost of `0`. From any value `u` with cost `c`, we can transition to `u + x^p` or `u - x^p`. The cost of adding a term `x^p` depends on whether it's the first term of the expression. - The first term `x^p` (where `p>0`) costs `p-1` operators (`x*...*x`). - The first term `x/x` (value 1, i.e., `p=0`) costs `1` operator. - Adding a term `x^p` (`p>0`) to an existing expression costs `p` operators (one for `+`/`-` and `p-1` for `*`). - Adding `x/x` to an existing expression costs `2` operators (one for `+`/`-` and one for `/`). The algorithm proceeds by repeatedly extracting the minimum-cost state from the priority queue and exploring its neighbors (next possible values) until the `target` is reached. ```java import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; class Solution { public int leastOpsExpressTarget(int x, int target) { // (cost, value) PriorityQueue pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); Map dist = new HashMap<>(); // Start with the initial terms we can form. // The first term x^p costs p-1 ops (p>0) or 1 op (p=0). pq.offer(new long[]{0, x}); // Term x, cost 0 dist.put((long)x, 0); long powerVal = x; int p = 1; while (powerVal < 2L * target) { // Term x^p pq.offer(new long[]{p, powerVal}); dist.put(powerVal, p); if (powerVal > (long)Integer.MAX_VALUE / x) break; // Avoid overflow powerVal *= x; p++; } // Term x/x = 1 pq.offer(new long[]{1, 1}); dist.put(1L, 1); while (!pq.isEmpty()) { long[] current = pq.poll(); int cost = (int)current[0]; long val = current[1]; if (val == target) { return cost; } if (cost > dist.getOrDefault(val, Integer.MAX_VALUE)) { continue; } // From `val`, we can add or subtract other terms. // The cost to add a term x^p to an existing expression is p ops. // The cost to add x/x is 2 ops. long termVal = x; int termPower = 1; while (termVal < 2L * target) { // Add term x^p long nextValAdd = val + termVal; int nextCostAdd = cost + 1 + termPower; if (nextCostAdd < dist.getOrDefault(nextValAdd, Integer.MAX_VALUE)) { dist.put(nextValAdd, nextCostAdd); pq.offer(new long[]{nextCostAdd, nextValAdd}); } // Subtract term x^p long nextValSub = val - termVal; int nextCostSub = cost + 1 + termPower; if (nextValSub > 0 && nextCostSub < dist.getOrDefault(nextValSub, Integer.MAX_VALUE)) { dist.put(nextValSub, nextCostSub); pq.offer(new long[]{nextCostSub, nextValSub}); } if (termVal > (long)Integer.MAX_VALUE / x) break; termVal *= x; termPower++; } // Add/Subtract term x/x = 1 long nextValAdd1 = val + 1; int nextCostAdd1 = cost + 2; if (nextCostAdd1 < dist.getOrDefault(nextValAdd1, Integer.MAX_VALUE)) { dist.put(nextValAdd1, nextCostAdd1); pq.offer(new long[]{nextCostAdd1, nextValAdd1}); } long nextValSub1 = val - 1; int nextCostSub1 = cost + 2; if (nextValSub1 > 0 && nextCostSub1 < dist.getOrDefault(nextValSub1, Integer.MAX_VALUE)) { dist.put(nextValSub1, nextCostSub1); pq.offer(new long[]{nextCostSub1, nextValSub1}); } } return -1; // Should not be reached } } ``` *Note: The provided Dijkstra implementation is slightly simplified for clarity. A fully robust solution might handle the first term logic differently (e.g., starting from 0) but the core idea remains the same.* ### Algorithm 1. Model the problem as finding the shortest path in a graph. The nodes of the graph are the integer values we can generate, and the edges are the operations. 2. The cost of an edge is the number of operators it represents. 3. Use Dijkstra's algorithm to find the shortest path from a starting value to the `target`. 4. We can start from value `0` and try to reach `target`. The cost to add the first term `x^p` is `p-1` operators (for `p>0`) or `1` operator (for `p=0`, i.e., `x/x`). 5. For any subsequent term added to a non-zero sum, the cost is `p` operators for `x^p` (`p>0`) and `2` operators for `x^0`. 6. Initialize a priority queue with the starting state, e.g., `(cost: 0, value: 0)`. A special initial cost like -1 can handle the first term logic gracefully. 7. Use a hash map `dist` to keep track of the minimum cost to reach each value, to avoid cycles and redundant computations. 8. While the priority queue is not empty, extract the state `(cost, value)` with the minimum cost. 9. If `value` is the `target`, we have found the shortest path. Return the cost. 10. From `value`, generate the next possible states by adding or subtracting terms `x^p` (for `p=0, 1, 2, ...`). Calculate the new cost and if it's better than the known distance, update `dist` and push the new state to the priority queue. # Solutions ### Java ```java class Solution { private int x; private Map f = new HashMap<>(); public int leastOpsExpressTarget(int x, int target) { this.x = x; return dfs(target); } private int dfs(int v) { if (x >= v) { return Math.min(v * 2 - 1, 2 * (x - v)); } if (f.containsKey(v)) { return f.get(v); } int k = 2; long y = (long)x * x; while (y < v) { y *= x; ++k; } int ans = k - 1 + dfs(v - (int)(y / x)); if (y - v < v) { ans = Math.min(ans, k + dfs((int)y - v)); } f.put(v, ans); return ans; } } ``` ### CPP ```cpp class Solution { public: int leastOpsExpressTarget(int x, int target) { unordered_map f; function dfs = [&](int v) -> int { if (x >= v) { return min(v * 2 - 1, 2 * (x - v)); } if (f.count(v)) { return f[v]; } int k = 2; long long y = x * x; while (y < v) { y *= x; ++k; } int ans = k - 1 + dfs(v - y / x); if (y - v < v) { ans = min(ans, k + dfs(y - v)); } f[v] = ans; return ans; }; return dfs(target); } }; ``` ### Python ```python class Solution: def leastOpsExpressTarget(self, x: int, target: int) -> int: @ cache def dfs(v: int) -> int: if x >= v: return min(v * 2 - 1, 2 * (x - v)) k = 2 while x ** k < v: k += 1 if x ** k - v < v: return min(k + dfs(x ** k - v), k - 1 + dfs(v - x ** (k - 1))) return k - 1 + dfs(v - x ** (k - 1)) return dfs(target) ```