LeetCode Solutions
964. Least Operators to Express Number
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
return dfs(x, target, {});
}
private:
int dfs(int x, int target, unordered_map<int, int>&& memo) {
if (memo.count(target))
return memo[target];
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 memo[target] = n;
int ans = dfs(x, target - prod / x, move(memo)) + n;
if (prod < 2 * target)
ans = min(ans, dfs(x, prod - target, move(memo)) + n + 1);
return memo[target] = ans;
}
};
class Solution {
public int leastOpsExpressTarget(int x, int target) {
return dfs(x, target);
}
private Map<Integer, Integer> memo = new HashMap<>();
private int dfs(int x, int target) {
if (memo.containsKey(target))
return memo.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) {
memo.put(target, n);
return memo.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);
memo.put(target, ans);
return ans;
}
}
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)