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:
/) returns rational numbers.-). 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 * 108Problem 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.
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.
This 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.
Python
Time Complexity: O(logxtarget) due to recursive calls and memoization.
Space Complexity: O(logxtarget) for the memoization table.
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.
This Java solution utilizes a dynamic programming map to store intermediate results and handle overlapping subproblems efficiently.
Java
Python
JavaScript
Time Complexity: O(logxtarget) due to memoization of subproblems.
Space Complexity: O(logxtarget) for the storage of intermediate results.
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.
This C++ solution utilizes an unordered_map to cache results. Similar to DP, it recursively exploits the nearest multiples to minimize the number of operators using power and modulo calculations.
Time Complexity: O(logxtarget) - logarithmic exploration based on division.
Space Complexity: O(logxtarget) for caching states.
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:
x^k - v geq v at this point, then we can only first obtain x^{k-1}, then recursively calculate dfs(v - x^{k-1}). The number of operators in this case is k - 1 + dfs(v - x^{k-1});x^k - v < v at this point, then we can obtain v in the above manner, with the number of operators being k - 1 + dfs(v - x^{k-1}); or we can first obtain x^k, then recursively calculate dfs(x^k - v), with the number of operators being k + 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}).
Python
Java
C++
Go
TypeScript
| 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. |
| Greedy Backtracking Approach | Time Complexity: O(logxtarget) - logarithmic exploration based on division. |
| Memoization Search | — |
| 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 |
花花酱 LeetCode 964. Least Operators to Express Number - 刷题找工作 EP237 • Hua Hua • 4,248 views views
Watch 5 more video solutions →Practice Least Operators to Express Number with our built-in code editor and test cases.
Practice on FleetCode