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)))