Least Operators to Express Number solution and explanation
4 more videos on this problem
花花酱 LeetCode 964. Least Operators to Express Number - 刷题找工作 EP237Hua Hua · 33:11 · 4K views
【每日一题】964. Least Operators to Express Number, 12/31/2019Huifeng Guan · 1:11:35 · 449 views
Leetcode 964. Least Operators to Express NumberAnnette Odingo · 25:26 · 283 views
No Sound Leetcode 964: Least Operators to Express NumberExtremeProgrammer · 2:14 · 44 views
LeetCode 964: Least Operators to Express NumberAlitaCode · 30:12 · 28 views
The 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 <= 1001 <= target <= 2 * 108
Approach overview
Problem Overview: You are given a number x and a target value. The task is to build the target using only the number x and operators +, -, *, and /. The goal is to minimize the number of operators used while respecting normal arithmetic precedence.
Approach 1: Recursive Approach with Memoization (Time: O(logx(target)), Space: O(logx(target)))
This method treats the problem as repeatedly decomposing the target using powers of x. For each target value, compute the closest power x^k. You then explore two choices: represent the target as x^k + remainder or overshoot using x^(k+1) and subtract the difference. A recursive function calculates the minimum operator count for each remainder while storing results in a memo table to avoid recomputation. The recursion depth stays proportional to log_x(target), making it efficient for large targets.
Approach 2: Dynamic Programming Using Base-x Representation (Time: O(logx(target)), Space: O(logx(target)))
This approach converts the target into base x. Each digit represents how many times a power of x contributes to the expression. You iterate through digits from least significant to most significant while maintaining two states: the cost of building the value directly and the cost if you carry to the next digit. Each step updates operator counts based on whether it is cheaper to add multiples of x^k or subtract from the next power. The DP transition captures the tradeoff between constructing the exact digit or adjusting via carry operations. This approach is deterministic and avoids recursion.
Approach 3: Greedy Backtracking with Power Selection (Time: O(logx(target)), Space: O(logx(target)))
The greedy idea selects the largest power of x that does not exceed the remaining target. After choosing that power, you recursively compute the cost of expressing the remainder. A second branch considers overshooting with the next power and subtracting the difference. Backtracking compares both paths and picks the minimum operator count. Although it looks greedy, the branching ensures correctness by evaluating both under- and over-approximation cases.
Recommended for interviews: The memoized recursion or the base-x dynamic programming solution is typically expected. They clearly demonstrate understanding of number decomposition and state reuse. The brute reasoning (choosing powers of x) shows intuition, while the optimized solution using memoization or dynamic programming highlights strong algorithmic design. The problem also relies heavily on number manipulation concepts from math.
Approach 1: Recursive Approach with Memoization
This approach involves recursively breaking down the target number into sums and differences of powers of the base number x. We utilize memoization to store the results of subproblems to avoid redundant calculations.
def leastOpsExpressTarget(x: int, target: int) -> int:
memo = {}
def calculate(t):
if t in memo:
return memo[t]
if t == 0:
return 0
if t < x:
return min(2 * t - 1, 2 * (x - t))
n = t // x
r = t % x
if r == 0:
op_count = calculate(n)
else:
op_count = min(calculate(n) + r, calculate(n + 1) + x - r)
memo[t] = op_count + 1
return memo[t]
return calculate(target) - 1This Python code recursively finds the minimum number of operations to express the target using powers of x. By storing intermediate results in a memoization table, it improves efficiency significantly.
Time Complexity: O(logxtarget) due to recursive calls and memoization.
Space Complexity: O(logxtarget) for the memoization table.
Approach 2: Dynamic Programming Approach
This approach uses dynamic programming to build up a solution iteratively. It constructs an array to store the minimal operators required for each subproblem up to the target.
public int leastOpsExpressTarget(int x, int target) {
Map<Integer, Integer> dp = new HashMap<>();
return helper(x, target, dp) - 1;
}
private int helper(int x, int target, Map<Integer, Integer> dp) {
if (dp.containsKey(target)) return dp.get(target);
if (target == 0) return 0;
if (target < x) return Math.min(2 * target - 1, 2 * (x - target));
int n = target / x;
int r = target % x;
int result;
if (r == 0) {
result = helper(x, n, dp);
} else {
result = Math.min(helper(x, n, dp) + r, helper(x, n + 1, dp) + x - r);
}
dp.put(target, result + 1);
return dp.get(target);
}This Java solution utilizes a dynamic programming map to store intermediate results and handle overlapping subproblems efficiently.
Time Complexity: O(logxtarget) due to memoization of subproblems.
Space Complexity: O(logxtarget) for the storage of intermediate results.
Approach 3: Dynamic Programming Approach
This approach uses dynamic programming to calculate the minimal number of operations needed to express the target using the base x. The idea is to recursively explore the possibilities of using the operations and cache results to avoid redundant calculations.
import functools
def leastOpsExpressTarget(x: int, target: int) -> int:
@functools.lru_cache(None)
def dp(t):
if t == 0: return 0
if t < x: return min(2 * t - 1, 2 * (x - t))
q, r = divmod(t, x)
return min(r + dp(q), (x - r) + dp(q + 1)) + 1
return dp(target) - 1var leastOpsExpressTarget = function(x, target) {
const dp = new Map();
const dfs = (t) => {
if (t === 0) return 0;
if (t < x) return Math.min(2 * t - 1, 2 * (x - t));
if (dp.has(t)) return dp.get(t);
const q = Math.floor(t / x);
const r = t % x;
const result = Math.min(r + dfs(q), (x - r) + dfs(q + 1)) + 1;
dp.set(t, result);
return result;
};
return dfs(target) - 1;
};The function uses an LRU cache to memoize results of the dp helper function to reduce recomputation. For each target t, we consider two cases by dividing it by x:
- If t is less than x, use either addition or subtraction to reach t.
- If t is greater than or equal to x, we try two routes: rounding down or up, and decide the minimal operators between those two cases.
- The recursion continues until we break t down to 0.
Time Complexity: O(logxtarget) - Recursive division breaks down the target logarithmically.
Space Complexity: O(logxtarget) due to recursion depth and memoization storage.
Approach 4: Greedy Backtracking Approach
This method uses backtracking with a greedy approach. The key is to choose the nearest power of x to either over or under target and recursively assess the number of operations needed.
import java.util.HashMap;
import java.util.Map;
class Solution {
private Map<Long, Integer> memo = new HashMap<>();
public int leastOpsExpressTarget(int x, long target) {
return dfs(x, target) - 1;
}
private int dfs(int x, long t) {
if (t == 0) return 0;
if (t < x) return (int)Math.min(2 * t - 1, 2 * (x - t));
if (memo.containsKey(t)) return memo.get(t);
long quotient = t / x, remainder = t % x;
int res = (int)Math.min(remainder + dfs(x, quotient), (x - remainder) + dfs(x, quotient + 1)) + 1;
memo.put(t, res);
return res;
}
}#include <unordered_map>
#include <algorithm>
class Solution {
std::unordered_map<int, int> cache;
public:
int leastOpsExpressTarget(int x, int target) {
return dfs(x, target) - 1;
}
int dfs(int x, int t) {
if (t == 0) return 0;
if (t < x) return std::min(2 * t - 1, 2 * (x - t));
if (cache.count(t)) return cache[t];
long quotient = t / x, remainder = t % x;
int res = std::min(remainder + dfs(x, quotient), (x - remainder) + dfs(x, quotient + 1)) + 1;
cache[t] = res;
return res;
}
};The Java implementation uses a HashMap for memoization. The dfs method attempts to minimize operations by considering:
- Where target is less than x, prefer straightforward addition or subtraction to construct the target.
- For targets at or beyond x, it recursively evaluates the best way either by reducing or increasing powers of x and stores these results.
Time Complexity: O(logxtarget) as the target gets recursively reduced.
Space Complexity: O(logxtarget) for the memoized maps.
Approach 5: Memoization Search
We define a function dfs(v), which represents the minimum number of operators needed to compose the number v using x. Then the answer is dfs(target).
The execution logic of function dfs(v) is as follows:
If x geq v, then we can obtain v by adding v instances of x / x, with the number of operators being v times 2 - 1; or we can obtain v by subtracting (x - v) instances of x / x from x, with the number of operators being (x - v) times 2. We take the minimum of the two.
Otherwise, we enumerate x^k starting from k=2 to find the first k where x^k geq v:
- If
x^k - v geq vat this point, then we can only first obtainx^{k-1}, then recursively calculatedfs(v - x^{k-1}). The number of operators in this case isk - 1 + dfs(v - x^{k-1}); - If
x^k - v < vat this point, then we can obtainvin the above manner, with the number of operators beingk - 1 + dfs(v - x^{k-1}); or we can first obtainx^k, then recursively calculatedfs(x^k - v), with the number of operators beingk + dfs(x^k - v). We take the minimum of the two.
To avoid redundant calculations, we implement the dfs function using memoization search.
The time complexity is O(log_{x}{target}) and the space complexity is O(log_{x}{target}).
function leastOpsExpressTarget(x: number, target: number): number {
const f: Map<number, number> = new Map();
const dfs = (v: number): number => {
if (x > v) {
return Math.min(v * 2 - 1, 2 * (x - v));
}
if (f.has(v)) {
return f.get(v)!;
}
let k = 2;
let y = x * x;
while (y < v) {
y *= x;
++k;
}
let ans = k - 1 + dfs(v - Math.floor(y / x));
if (y - v < v) {
ans = Math.min(ans, k + dfs(y - v));
}
f.set(v, ans);
return ans;
};
return dfs(target);
}func leastOpsExpressTarget(x int, target int) int {
f := map[int]int{}
var dfs func(int) int
dfs = func(v int) int {
if x > v {
return min(v*2-1, 2*(x-v))
}
if val, ok := f[v]; ok {
return val
}
k := 2
y := x * x
for y < v {
y *= x
k++
}
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)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(logxtarget) due to recursive calls and memoization. |
| Dynamic Programming Approach | Time Complexity: O(logxtarget) due to memoization of subproblems. |
| Dynamic Programming Approach | Time Complexity: O(logxtarget) - Recursive division breaks down the target logarithmically. |
| Greedy Backtracking Approach | Time Complexity: O(logxtarget) as the target gets recursively reduced. |
| Memoization Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(log_x(target)) | O(log_x(target)) | General case; clean recursive formulation with cached subproblems |
| Dynamic Programming (Base-x) | O(log_x(target)) | O(log_x(target)) | Best for iterative implementations and language environments where recursion depth is limited |
| Greedy Backtracking | O(log_x(target)) | O(log_x(target)) | Good for understanding the power-selection intuition behind the optimal solution |
Frequently asked questions
Is Least Operators to Express Number easy or hard?
Least Operators to Express Number is classified as a Hard problem on LeetCode. The challenge comes from modeling arithmetic expressions using powers of x and minimizing operators through recursive or dynamic programming state transitions.
Least Operators to Express Number Python/Java solution
Python implementations often use recursion with functools.lru_cache for memoization. Java solutions typically use a HashMap for caching or an iterative DP approach based on base-x digits. Both implementations achieve O(log_x(target)) complexity.
How to solve Least Operators to Express Number in O(log n)?
Convert the target into base-x representation or recursively break it using powers of x. At each step, decide whether to build the current power exactly or overshoot using the next power and subtract the difference. Memoization or DP ensures each state is computed once, resulting in O(log_x(target)) complexity.
What is the best approach for Least Operators to Express Number?
The most common optimal approach uses memoized recursion or dynamic programming based on powers of x. The algorithm repeatedly decomposes the target using the nearest power of x and computes the minimum operator cost for the remaining value. Both strategies run in O(log_x(target)) time because the target shrinks by powers of x at each step.
Is Least Operators to Express Number asked at Google/Amazon/Meta?
This problem is tagged as a hard math and dynamic programming problem and is commonly associated with high-level algorithm interviews at companies like Google and Meta. It tests number decomposition, recursion optimization, and DP state design.
What data structure is used in Least Operators to Express Number?
The key structure is a memoization map or DP array storing the minimum operator cost for intermediate targets. The algorithm also relies on mathematical computation of powers of x while decomposing the target value.
What is the time complexity of Least Operators to Express Number?
The optimal solutions run in O(log_x(target)) time and space. Each recursive or DP state corresponds to a power level of x while decomposing the target value, so the number of states grows with the logarithm of the target in base x.