[
math
dp
greedy
]
Leetcode 0964. Least Operators to Express Number
Problem statement
https://leetcode.com/problems/least-operators-to-express-number/
Solution
Consider say number 287
, which we want to construct using number 5
. Then we need to choose the biggest power of 5
, that is 125
and look at numbers 250
and 375
. Now we have candidates 37
and 88
. We repeat process for those numbers, for 37
we have candidates 12, 13
and for number 88
we also have candidates 13, 12
. Notice, that it will happen always: on each layer we will have no more than 2
candidates. No, we can do it either with recursion or loop, or with dp(x, target, idx)
is the state where target
is current target we want to get and idx
is the biggest power of x
we deal with now.
Complexity
It is O(log x)
for time and space.
Code
class Solution:
def leastOpsExpressTarget(self, x, target):
@lru_cache(None)
def dp(target, idx):
if idx == 0 or target == 1:
return target * 2 - 1
power = x**idx
cnt = target // power
low = idx * cnt + dp(target - power * cnt, idx - 1)
high = idx * (cnt + 1) + dp(power * (cnt + 1) - target, idx - 1)
return min(low, high)
return dp(target, ceil(log(target, x)))