964. Least Operators to Express Number LeetCode Solution
In this guide, you will get 964. Least Operators to Express Number LeetCode Solution with the best time and space complexity. The solution to Least Operators to Express Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Least Operators to Express Number
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.
964. Least Operators to Express Number LeetCode Solution in C++
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
return dfs(x, target, {});
}
private:
int dfs(int x, int target, unordered_map<int, int>&& mem) {
if (const auto it = mem.find(target); it != mem.cend())
return it->second;
if (x > target)
return min(2 * target - 1, 2 * (x - target));
if (x == target)
return 0;
long prod = x;
int n = 0;
while (prod < target) {
prod *= x;
++n;
}
if (prod == target)
return mem[target] = n;
int ans = dfs(x, target - prod / x, std::move(mem)) + n;
if (prod < 2 * target)
ans = min(ans, dfs(x, prod - target, std::move(mem)) + n + 1);
return mem[target] = ans;
}
}; /* code provided by PROGIEZ */
964. Least Operators to Express Number LeetCode Solution in Java
class Solution {
public int leastOpsExpressTarget(int x, int target) {
return dfs(x, target);
}
private Map<Integer, Integer> mem = new HashMap<>();
private int dfs(int x, int target) {
if (mem.containsKey(target))
return mem.get(target);
if (x > target)
return Math.min(2 * target - 1, 2 * (x - target));
if (x == target)
return 0;
long prod = x;
int n = 0;
while (prod < target) {
prod *= x;
++n;
}
if (prod == target) {
mem.put(target, n);
return mem.get(target);
}
int ans = dfs(x, target - (int) (prod / (long) x)) + n;
if (prod < 2 * target)
ans = Math.min(ans, dfs(x, (int) (prod - (long) target)) + n + 1);
mem.put(target, ans);
return ans;
}
} // code provided by PROGIEZ
964. Least Operators to Express Number LeetCode Solution in Python
class Solution:
def leastOpsExpressTarget(self, x: int, target: int) -> int:
@functools.lru_cache(None)
def dfs(target):
if x > target:
return min(2 * target - 1, 2 * (x - target))
if x == target:
return 0
prod = x
n = 0
while prod < target:
prod *= x
n += 1
if prod == target:
return n
ans = dfs(target - prod // x) + n
if prod < 2 * target:
ans = min(ans, dfs(prod - target) + n + 1)
return ans
return dfs(target) # code by PROGIEZ
