964. Least Operators to Express Number
Problem Description
The problem presents a situation where we need to find the minimum number of operations required to achieve a target number starting with a given positive integer x
. The only allowed operations are addition (+
), subtraction (-
), multiplication (*
), and division (/
), and x
can be used repeatedly in the expression. The challenge is to construct an expression using the fewest possible operations such that the result of the expression is equal to the target number provided.
The constraints are as follows:
- Division results in rational numbers.
- No parentheses allowed in the expression.
- Standard order of operations is followed (multiplication and division precede addition and subtraction).
- Unary negation is not permitted.
The goal is to return the least number of operators used in an expression that equals the target number.
Intuition
To solve this problem, a depth-first search (DFS) algorithm can be used with the help of dynamic programming to store intermediate results. This is because the problem has an overlapping subproblem structure and possesses optimal substructure properties, which are both hallmark traits that benefit from dynamic programming optimization.
We understand that larger numbers can be more efficiently created by multiplication, especially if x
is large. However, as the number gets closer to the target, it might be more efficient to use addition or subtraction instead of multiplication or division.
The solution involves recursively trying to build up from smaller numbers to the target, using dynamic programming to avoid recalculating subproblems. For each step, the current value could be built by either adding x
, subtracting x
, multiplying by x
, or dividing by x
. However, the algorithm wisely narrows down the choices by considering that division is not optimal compared to other operations since it requires more operations to get integers unless explicitly needed.
The dfs
function calculates the minimum number of operations needed to reach a number v
by comparing the cost (in terms of the number of operations) of reaching v
by multiplying x
to itself some number of times then adding or subtracting x
to this product. It handles the base case when v
is less than x
, and it uses recursion for larger values of v
by finding the least number of operators required for x**k
closest to but not smaller than v
, and also for x**(k-1)
.
The @cache
decorator is a Python technique that automatically stores the results of each call to the dfs
function to avoid redundant calculations during the search, thereby speeding up the entire process.
By considering these options, the algorithm minimizes the number of operations at each step and ultimately finds the least number of operations to reach the target number from x
.
Learn more about Memoization, Math and Dynamic Programming patterns.
Solution Approach
The solution implements a recursive depth-first search (DFS) algorithm with a dynamic programming approach. It employs memoization to save the results of intermediate computations using Python's @cache
decorator. The core of the problem is the dfs
function, which uses recursion to determine the minimum number of operations required to express any intermediate value v
that will eventually lead to the target.
Here's a step-by-step breakdown of the dfs
function in the code:
-
Return base case for small
v
: When the current valuev
that needs to be expressed is less than or equal tox
, the base case logic calculates the number of operations needed by usingx
either through direct multiplication/addition or subtraction. This is done by the expressionsmin(v * 2 - 1, 2 * (x - v))
, which represent the two possible ways to get tov
using the fewest operations: either by addingx
to itselfv
times (v * 2 - 1
accounts for the operations) or combining(x - v)
subtractions with additions to achieve a shorter path, which might be more optimal asv
gets closer tox
. -
Determine power of
x
required: Ifv
is greater thanx
, the function computes the smallest exponentk
such thatx**k
is the smallest power ofx
that is just greater than or equal tov
. This step is necessary because creating large numbers by multiplyingx
by itself is more operationally efficient than addingx
repeatedly. -
Recursive calls to strategy: Once
k
is found, there are two main scenarios catered to by the recursive calls:- If
x**k - v
is less thanv
, this implies that it may be more efficient to reachx**k
first and then to subtract the difference tov
. The recursive calldfs(x**k - v)
calculates the minimal operations to reach fromx**k
tov
, whilek + dfs(x**k - v)
includes the operations to get tox**k
. This case also contemplates an alternative, which is not getting entirely tox**k
but tox**(k-1)
and then add up from there (k - 1 + dfs(v - x ** (k - 1))
). - If
x**k - v
is greater than or equal tov
, the algorithm only considers using the alternative approach of reachingx**(k-1)
first (k - 1 + dfs(v - x ** (k - 1))
).
- If
-
Memoization: The
@cache
decorator above thedfs
function is responsible for memorizing the results of recursive calls. This ensures that if a particular value ofv
is reached multiple times during the recursive exploration, its minimum number of operations is calculated only once and reused, which drastically reduces computation time.
Finally, the dfs
function is called with the initial target, and the result represents the least number of operators required to reach the target from x
.
This algorithm leverages recursion, memoization, and mathematical power operations to effectively explore and calculate the minimum number of steps required to reach the desired result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach, considering the problem's statement and intuition. Suppose our starting number x
is 3
, and our target number is 19
. The goal is to find out the least number of operations needed to reach 19
from 3
using addition, subtraction, multiplication, and division only. Let’s walk through how the dfs
function would work for this example.
-
Base Case: When the function is called with
v
which is less than or equal tox
, it returns the minimum steps to reachv
using either multiple additions or a near equal number of subtractions and additions, whichever is fewer. But in our example,19
is bigger than3
, so we do not consider this case initially. -
Determining the Power of
x
: Since19
is more significant than3
, we look for the smallest power ofx
(3
in this case) that is just greater than or equal to19
. We find out that3
to the power of3
(3**3
or27
) is the smallest power of3
greater than19
. So,k=3
in this scenario. -
Recursive Strategy:
-
Subtraction First: We compute
3**k - v
, which results in27 - 19 = 8
. Because8
is less than19
, we can reach27
by multiplying3
by itself3
times and then subtract8
. To reach8
, we would calldfs(8)
. Here,8
is twice3
(ourx
) plus2
(3*2 + 2 = 8
). So, to get to8
, we would need4
operations (two multiplications and two additions). Adding3
for the previous multiplications to get to27
, we have7
operations in total so far to get from3
to19
this way. -
Addition First: We also consider reaching
3^(k-1)
, which is3**2
or9
, and then add up from there. To get from9
to19
, we need to perform10
operations (9 + 3 + 3 + 3 + 3
). Including the two multiplications to get to9
, we have12
operations, which is more than the7
operations from the subtraction approach.
-
-
Memoization: The
@cache
decorator ensures results ofdfs(v)
are stored. For example, whendfs(8)
is calculated, if8
is required at another point, it won't need to be recalculated, thus, saving computation time.
Given these two strategies and considering memoization that reduces redundant calculations, the algorithm will decide that for x = 3
and target 19
, the least number of operations to get the target from x
would be 7
: 3 * 3 * 3 - 3 - 3 - 3 - 2
.
In summary, starting with 3
, to get to 19
with the fewest operators, it's optimal to first hit a power of x
closest but above the target (27
), then use subtraction to reduce to the target. The algorithm effectively computes this using recursion and dynamic programming techniques.
Solution Implementation
1from functools import lru_cache
2
3class Solution:
4 def leastOpsExpressTarget(self, x: int, target: int) -> int:
5 # Use caching to avoid recomputing results for the same value
6 @lru_cache(maxsize=None) # Using LRUCache instead of `cache` (Python 3.9+ feature)
7 def dfs(current_value: int) -> int:
8 # If x is greater than or equal to the current_value, find the minimal operations required
9 if x >= current_value:
10 # Calculate the number of operations when adding x or subtracting from x
11 return min(current_value * 2 - 1, (x - current_value) * 2)
12
13 # Initialize multiplier k to 2 as x**1 has been checked above
14 k = 2
15 # Find k such that x**k is just greater than current_value
16 while x ** k < current_value:
17 k += 1
18
19 # If the power raised to k is very close to current_value, decide to add or subtract
20 if x ** k - current_value < current_value:
21 # Take the minimum of either subtracting the next power or adding the previous power
22 return min(k + dfs(x ** k - current_value),
23 k - 1 + dfs(current_value - x ** (k - 1)))
24
25 # Otherwise, always subtract current_value from the previous power
26 return k - 1 + dfs(current_value - x ** (k - 1))
27
28 # Start the recursive function with the initial target value
29 return dfs(target)
30
1class Solution {
2 private int base;
3 private Map<Integer, Integer> memo = new HashMap<>();
4
5 public int leastOpsExpressTarget(int x, int target) {
6 this.base = x;
7 return dfs(target);
8 }
9
10 private int dfs(int value) {
11 // If the base is greater or equal to the value, we have two expressions:
12 // 1) Using '+' base 'value' times: (x/x + x/x + ... + x/x)
13 // 2) Using '-' once and '+' (base-value) times: (x - x/x - x/x - ...)
14 if (base >= value) {
15 return Math.min(value * 2 - 1, 2 * (base - value));
16 }
17 // If we have already computed the minimum operations for this value, return it
18 if (memo.containsKey(value)) {
19 return memo.get(value);
20 }
21 // Start with exponent 'k' at 2 because we have x^1 = x already
22 int exponent = 2;
23 // Calculate x^exponent while it's less than the 'value'
24 long power = (long) base * base;
25 while (power < value) {
26 power *= base;
27 ++exponent;
28 }
29 // The result is either by subtracting the value from the power of x found
30 // Or by adding more to reach the power of x and then subtracting the target value from it
31 int operations = exponent - 1 + dfs(value - (int) (power / base));
32 // Check if we should also consider the case where the power exceeds the value
33 if (power - value < value) {
34 operations = Math.min(operations, exponent + dfs((int) power - value));
35 }
36 // Store the result in memoization map for future reference
37 memo.put(value, operations);
38 return operations;
39 }
40}
41
1#include <functional>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 // Method to find the least number of operations to express the target using integers and the number x.
8 int leastOpsExpressTarget(int x, int target) {
9 // We use a map to memoize the results of subproblems.
10 unordered_map<int, int> memo;
11
12 // A recursive function, defined using a lambda, that does the work.
13 // It calculates the least number of operations to express 'value'.
14 function<int(int)> dfs = [&](int value) -> int {
15 // If x is greater than or equal to the target value, we calculate the minimum number of operations.
16 if (x >= value) {
17 return min(value * 2 - 1, 2 * (x - value));
18 }
19 // Check if the result has been memoized; if so, return it.
20 if (memo.count(value)) {
21 return memo[value];
22 }
23 int opCount = 2; // The operation count starts at 2 (representing x/x).
24 long long power = x * x; // Start with x squared.
25
26 // Increase 'power' by multiplying with x until it just exceeds or equals 'value'.
27 while (power < value) {
28 power *= x;
29 ++opCount; // Increment operation count each time we multiply with x.
30 }
31
32 // Compute the minimum operations if we use 'power' just less than 'value':
33 int ans = opCount - 1 + dfs(value - power / x);
34 // If the remaining value (power - value) is less than the original 'value',
35 // it might be more optimal to also consider this path.
36 if (power - value < value) {
37 ans = min(ans, opCount + dfs(power - value));
38 }
39
40 // Memoize the answer for 'value'.
41 memo[value] = ans;
42 return ans;
43 };
44 // Start the recursive function with the target value.
45 return dfs(target);
46 }
47};
48
1/**
2 * A recursive function to compute the minimum number of operations required
3 * to express the target number using the base number 'x', given the constraints of the problem.
4 *
5 * @param x The base number used for expressions.
6 * @param target The target number to be expressed.
7 * @return The minimum number of operations needed.
8 */
9function leastOpsExpressTarget(x: number, target: number): number {
10 // A map that caches the minimum number of operations for given target values.
11 const numOperationsCache: Map<number, number> = new Map();
12
13 // The depth-first search function that calculates the number of operations recursively.
14 const dfs = (currentTarget: number): number => {
15 // If x is greater than the current target, calculate the minimum operations directly.
16 if (x > currentTarget) {
17 return Math.min(currentTarget * 2 - 1, (x - currentTarget) * 2);
18 }
19 // If the result for the current target is already in the cache, return it.
20 if (numOperationsCache.has(currentTarget)) {
21 return numOperationsCache.get(currentTarget)!;
22 }
23 // Initialize 'k' and 'y' for the power expression of 'x'.
24 let powerIndex = 2;
25 let poweredX = x * x;
26 // Increase the power of 'x' until it is greater than or equal to the current target.
27 while (poweredX < currentTarget) {
28 poweredX *= x;
29 powerIndex++;
30 }
31 // Calculate the minimum operations required when using one less power of 'x'.
32 let minimumOperations = powerIndex - 1 + dfs(currentTarget - Math.floor(poweredX / x));
33 // Consider the case where the remainder (y - v) is smaller than the target.
34 if (poweredX - currentTarget < currentTarget) {
35 minimumOperations = Math.min(minimumOperations, powerIndex + dfs(poweredX - currentTarget));
36 }
37 // Store the calculated result in the cache.
38 numOperationsCache.set(currentTarget, minimumOperations);
39 // Return the calculated minimum operations.
40 return minimumOperations;
41 };
42
43 // Start the recursion with the target number.
44 return dfs(target);
45}
46
Time and Space Complexity
The provided Python code defines a function called leastOpsExpressTarget
to find the least number of operations needed to express any number target
using only integers, the operations +
, -
and multiplication by x
, excluding any operation on numbers themselves to get a digit out of them.
Time Complexity:
The time complexity of this code is difficult to determine exactly without more information on the properties of the number x
and the target
, as the number of recursive calls to the dfs
function depends on how these numbers relate to each other. However, we can discuss the broad factors affecting the time complexity:
-
We perform a recursive depth-first search (DFS) via the
dfs
function. -
For each recursive call to
dfs
, we search for the smallestk
such thatx**k >= v
, wherev
decreases with each recursion. In the worst case, this search could potentially be linear with respect to the logarithm ofv
basex
, i.e.,O(log_x(v))
. It would be the height of the recursion. -
At each recursive call, if
x**k != v
, we have up to two recursive calls:dfs(x**k - v)
ordfs(v - x ** (k - 1))
. -
The use of caching (memoization via
@cache
) improves the time complexity significantly by avoiding repeated calculation for the samev
values.
Considering the caching and the logarithmic height of the recursion tree, the overall time complexity is expected to be O(log_x(target) * log_x(target)). This is because there are at most O(log_x(target))
levels and each level could potentially cause two recursive calls.
Space Complexity:
The space complexity of this algorithm is primarily determined by the cache and the call stack used for recursion.
-
The cache will store at most
O(log_x(target))
states, as it caches results for each distinct value ofv
that it encounters. -
The recursion call stack will at most be
O(log_x(target))
deep since that's the maximum depth we can recurse beforev
becomes smaller thanx
.
Therefore, the space complexity is O(log_x(target)), dominated by the stack space required for recursion and the additional space for caching the results.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.