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 * 108The key challenge in #964 Least Operators to Express Number is minimizing the number of operators required to build a target value using only a given number x. A common strategy is to think in terms of powers of x, since multiplication naturally generates values like x^1, x^2, x^3, and so on.
A useful insight is to represent the target in a form similar to base-x decomposition. At each step, you decide whether to construct the current power directly or overshoot with a higher power and adjust using subtraction. This leads to overlapping subproblems, making dynamic programming with memoization an effective approach.
The recursive state typically represents the minimum number of operators required to build a remaining value. By caching intermediate results, repeated computations are avoided and the search space remains manageable. Careful cost calculation for multiplication, addition, and subtraction operations helps determine the optimal expression.
The optimized memoized approach generally runs in about O(log target) states with small transitions, giving roughly O((log target)^2) time complexity and O(log target) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Math + Dynamic Programming with Memoization | O((log target)^2) | O(log target) |
CrioDo
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of math and dynamic programming problems like this one appear in FAANG-level interviews. The question tests recursion, memoization, mathematical decomposition, and optimization thinking, which are common interview themes.
The optimal approach combines mathematical reasoning with dynamic programming and memoization. By expressing the target relative to powers of x and exploring both undershoot and overshoot cases, the algorithm minimizes the number of operators. Memoization prevents recomputation of subproblems.
Dynamic programming is useful because the problem contains overlapping subproblems when computing the minimal operators for intermediate values. Memoization stores results for previously computed targets, significantly reducing redundant calculations.
A hash map or dictionary is commonly used for memoization to store the minimum operator count for intermediate values. This allows constant-time lookup and ensures the recursive DP solution remains efficient.