Least Operators to Express Number

Hard

#0918Time: 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.1 company

Patterns

Math Dynamic Programming Memoization

Companies

Snap

Prompt

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 * 10⁸

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Define a recursive function, say findMinOperators(currentValue), which calculates the minimum operators to reach target from currentValue.
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.
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 -).
The function returns the minimum cost among all possible next steps.
To avoid recomputing results for the same currentValue, memoization (a hash map) can be used to store the results.

Walkthrough

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).

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    Map<Integer, Integer> memo;6    int x_val;7 8    public int leastOpsExpressTarget(int x, int target) {9        this.memo = new HashMap<>();10        this.x_val = x;11        // We start from x, so we need one less operator than the number of x's used.12        // The cost of x itself is 0 operators.13        // The problem can be rephrased as finding min ops to get target from 0,14        // where the first term x^k costs k-1 ops, and subsequent terms cost k ops.15        // This is complex. A simpler model is to find min ops to get target from x.16        return solve(target);17    }18 19    private int solve(int currentTarget) {20        if (currentTarget == 0) return -1; // Should not happen if we start from x21        if (currentTarget == x_val) return 0;22        if (memo.containsKey(currentTarget)) return memo.get(currentTarget);23 24        long power = x_val;25        int p = 1;26        int minOps = Integer.MAX_VALUE;27 28        // Case 1: target = x * ... * x + ...29        // We try to reach target from a smaller value by multiplication30        if (currentTarget > x_val && currentTarget % x_val == 0) {31            minOps = Math.min(minOps, solve(currentTarget / x_val) + 1);32        }33 34        // Case 2: target = x + ... + x35        if (currentTarget > x_val && currentTarget % x_val != 0) { // Simplified heuristic36             minOps = Math.min(minOps, solve(currentTarget - x_val) + 1);37        }38        39        // This is a highly simplified and incorrect recursive solution to illustrate the idea.40        // A full brute-force would be much more complex.41        memo.put(currentTarget, minOps);42        return minOps;43    }44}

Note: The provided code is a conceptual illustration and not a complete or correct brute-force solution, which would be significantly more complex.

Complexity

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.

Trade-offs

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.

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.

Algorithm

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.
The cost of an edge is the number of operators it represents.
Use Dijkstra's algorithm to find the shortest path from a starting value to the target.
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).
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.
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.
Use a hash map dist to keep track of the minimum cost to reach each value, to avoid cycles and redundant computations.
While the priority queue is not empty, extract the state (cost, value) with the minimum cost.
If value is the target, we have found the shortest path. Return the cost.
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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3import java.util.PriorityQueue;4 5class Solution {6    public int leastOpsExpressTarget(int x, int target) {7        // (cost, value)8        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));9        Map<Long, Integer> dist = new HashMap<>();10 11        // Start with the initial terms we can form.12        // The first term x^p costs p-1 ops (p>0) or 1 op (p=0).13        pq.offer(new long[]{0, x}); // Term x, cost 014        dist.put((long)x, 0);15 16        long powerVal = x;17        int p = 1;18        while (powerVal < 2L * target) {19            // Term x^p20            pq.offer(new long[]{p, powerVal});21            dist.put(powerVal, p);22            if (powerVal > (long)Integer.MAX_VALUE / x) break; // Avoid overflow23            powerVal *= x;24            p++;25        }26        // Term x/x = 127        pq.offer(new long[]{1, 1});28        dist.put(1L, 1);29 30        while (!pq.isEmpty()) {31            long[] current = pq.poll();32            int cost = (int)current[0];33            long val = current[1];34 35            if (val == target) {36                return cost;37            }38 39            if (cost > dist.getOrDefault(val, Integer.MAX_VALUE)) {40                continue;41            }42 43            // From `val`, we can add or subtract other terms.44            // The cost to add a term x^p to an existing expression is p ops.45            // The cost to add x/x is 2 ops.46 47            long termVal = x;48            int termPower = 1;49            while (termVal < 2L * target) {50                // Add term x^p51                long nextValAdd = val + termVal;52                int nextCostAdd = cost + 1 + termPower;53                if (nextCostAdd < dist.getOrDefault(nextValAdd, Integer.MAX_VALUE)) {54                    dist.put(nextValAdd, nextCostAdd);55                    pq.offer(new long[]{nextCostAdd, nextValAdd});56                }57 58                // Subtract term x^p59                long nextValSub = val - termVal;60                int nextCostSub = cost + 1 + termPower;61                 if (nextValSub > 0 && nextCostSub < dist.getOrDefault(nextValSub, Integer.MAX_VALUE)) {62                    dist.put(nextValSub, nextCostSub);63                    pq.offer(new long[]{nextCostSub, nextValSub});64                }65 66                if (termVal > (long)Integer.MAX_VALUE / x) break;67                termVal *= x;68                termPower++;69            }70            71            // Add/Subtract term x/x = 172            long nextValAdd1 = val + 1;73            int nextCostAdd1 = cost + 2;74            if (nextCostAdd1 < dist.getOrDefault(nextValAdd1, Integer.MAX_VALUE)) {75                dist.put(nextValAdd1, nextCostAdd1);76                pq.offer(new long[]{nextCostAdd1, nextValAdd1});77            }78 79            long nextValSub1 = val - 1;80            int nextCostSub1 = cost + 2;81            if (nextValSub1 > 0 && nextCostSub1 < dist.getOrDefault(nextValSub1, Integer.MAX_VALUE)) {82                dist.put(nextValSub1, nextCostSub1);83                pq.offer(new long[]{nextCostSub1, nextValSub1});84            }85        }86        return -1; // Should not be reached87    }88}

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.

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int x;4private5  Map<Integer, Integer> f = new HashMap<>();6public7  int leastOpsExpressTarget(int x, int target) {8    this.x = x;9    return dfs(target);10  }11private12  int dfs(int v) {13    if (x >= v) {14      return Math.min(v * 2 - 1, 2 * (x - v));15    }16    if (f.containsKey(v)) {17      return f.get(v);18    }19    int k = 2;20    long y = (long)x * x;21    while (y < v) {22      y *= x;23      ++k;24    }25    int ans = k - 1 + dfs(v - (int)(y / x));26    if (y - v < v) {27      ans = Math.min(ans, k + dfs((int)y - v));28    }29    f.put(v, ans);30    return ans;31  }32}

1class Solution {2public:3  int leastOpsExpressTarget(int x, int target) {4    unordered_map<int, int> f;5    function<int(int)> dfs = [&](int v) -> int {6      if (x >= v) {7        return min(v * 2 - 1, 2 * (x - v));8      }9      if (f.count(v)) {10        return f[v];11      }12      int k = 2;13      long long y = x * x;14      while (y < v) {15        y *= x;16        ++k;17      }18      int ans = k - 1 + dfs(v - y / x);19      if (y - v < v) {20        ans = min(ans, k + dfs(y - v));21      }22      f[v] = ans;23      return ans;24    };25    return dfs(target);26  }27};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem