Least Operators to Express Number LeetCode solution in Python

1
# Runtime: 3027 ms (Top 7.32%) | Memory: 13.9 MB (Top 97.56%)
2
class Solution(object):
3
    def leastOpsExpressTarget(self, x, target):
4
        return self.cost(x, target)
5

6
    def cost(self, x, val):
7
        if val == x:
8
            return 0
9
        elif val < x:
10
            # two possible states
11
            # either val > x / 2: we substract 1s
12
            state_1 = 2 * (x - val)
13
            # or val < x / 2: we divide once to 1 and we add enough 1s
14
            state_2 = 2 * val - 1
15
            return min(state_1, state_2)
16
        else:
17
            # there is a maximum power of x that we can add
18
            p = int(log(val) // log(x))
19
            # and either x^p or x^(p+1) is the closest
20
            a = x**p
21
            b = a * x
22
            if b < 2 * val:
23
                # x**(p+1) - val < val - x**p
24
                return min(p + self.cost(x, val - a), p + 1 + self.cost(x, b - val))
25
            else:
26
                return p + self.cost(x, val - a)