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 happens before addition and subtraction.
It's 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.
 

Example 1:
Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.

Example 2:

Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.


Example 3:
Input: x = 100, target = 100000000
Output: 3
Explanation: 100 * 100 * 100 * 100.  The expression contains 3 operations.
 



Note:

2 <= x <= 100
1 <= target <= 2 * 10^8

Difficulty: interview

Starter code:

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        

Solutions:
class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        def dp(i, j):
            if i==0: return 2*j
            # if j==0: return 0
            if j==1: return 2
            if (i, j) in memo: return memo[(i, j)]
            base = x**i
            q, r = divmod(j, base)
            if r==0: return q*i
            memo[(i, j)]=min(q*i+dp(i-1, r), (q+1)*i+dp(i-1, base-r))
            return memo[(i, j)]
        
        memo = {}
        return dp(ceil(log(target, x)), target)-1

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        @lru_cache(None)
        def calc(goal):
            if x == goal:
                return 0
            if x > goal:
                return min(goal*2 - 1, (x - goal) * 2)
            
            sums = x
            times = 0
            while sums < goal:
                times += 1
                sums *= x
            
            if sums == goal:
                return times
            
            if sums - goal < goal:
                return min(calc(sums - goal) + times + 1, calc(goal - (sums // x)) + times)
            
            return calc(goal - (sums // x)) + times            
            
        return calc(target)

from functools import lru_cache
class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        @lru_cache(None)
        def search(t: int) -> int:
            if x == t:
                return 0
            if t < x:
                d1, d2 = t, x - t
                return min(2 * d1 - 1, 2 * d2)
            k1 = int(math.log(t, x))
            y1 = x ** k1
            if y1 == t:
                return k1 - 1
            total = k1 + search(t - y1)
            k2 = k1 + 1
            y2 = x ** k2
            if y2 <= 2 * t - y1:
                total = min(total, k2 + search(y2 - t))
            return total
        
        return search(target)

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        q, s = [], set()
        q.append((0, target))
        while q:
            c, t = heapq.heappop(q)
            if t == 0: return c - 1
            if t in s: continue
            s.add(t)
            n = int(log(t) / log(x)) 
            l = t - x**n
            heapq.heappush(q, (c+(2 if n==0 else n), l))
            r = x**(n+1) - t
            heapq.heappush(q, (c + n + 1, r))


class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        import math
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def f(x, target, depth):
            # print('  ' * depth, '开始计算', x, target)
            if target == 1:
                return 1

            res = target * 2 - 1
            if target < x:
                if x - target < target:
                    res = min(res, 1 + f(x, x - target, depth + 1))
            else:
                y = math.log(target, x)
                y_lower = int(y)
                p = pow(x, y_lower)
                cnt = target // p
                remain = target - cnt * p
                if y > y_lower:
                    res = min(res, y_lower * cnt + f(x, remain, depth + 1))
                    if p * x - target < target:
                        res = min(res, y_lower + 1 + f(x, p * x - target, depth + 1))
                else:
                    res = y_lower - 1
            return res

        return f(x, target, 0)

class Solution:
    def leastOpsExpressTarget(self, x, y):
        pos = neg = k = 0
        while y:
            y, cur = divmod(y, x)
            if k:
                pos, neg = min(cur * k + pos, (cur + 1) * k + neg), min((x - cur) * k + pos, (x - cur - 1) * k + neg)
            else:
                pos, neg = cur * 2, (x - cur) * 2
            k += 1
        return min(pos, k + neg) - 1

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        
        cost = list(range(40))
        cost[0] = 2
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(i, target) :
            if target == 0 : return 0
            if target == 1 : return cost[i]
            
            if i >= 39 : return float('inf')
            
            t, r = divmod(target, x)
            return min(r * cost[i] + dp(i + 1, t), (x - r) * cost[i] + dp(i + 1, t + 1))
        
        return dp(0, target) - 1
        
        


class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        
        cost = list(range(32))
        cost[0] = 2
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(i, target) :
            if target == 0 : return 0
            if target == 1 : return cost[i]
            
            if i >= 31 : return float('inf')
            
            t, r = divmod(target, x)
            return min(r * cost[i] + dp(i + 1, t), (x - r) * cost[i] + dp(i + 1, t + 1))
        
        return dp(0, target) - 1
        
        


from functools import lru_cache
class Solution:
    @lru_cache(None)
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        if x == target:
            return 0
        if x > target:
            return min(target*2-1,(x-target)*2)
        sums, cnt = x, 0
        while sums < target:
            sums *= x 
            cnt += 1
        if sums == target:
            return cnt
        left, right = float('inf'), float('inf')
        if sums - target < target:
            right = self.leastOpsExpressTarget(x, sums-target) + cnt + 1
        left = self.leastOpsExpressTarget(x, target-sums//x) + cnt
        return min(left,right)

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        dp = {}
        def dfs(i, target):
            if i in dp and target in dp[i]:
                return dp[i][target]
            if target == 0:
                return 0
            if i >= 32:
                return float('inf')
            div = x ** i
            res = target % div
            ret = min(dfs(i + 1, target - res) + res * x // div * (i - 1),
                       dfs(i + 1, target - res + div) + (div - res) * x // div * (i - 1))
            if res == 0:
                ret = min(ret, target // div * i)
            dp[i] = dp.get(i, {})
            dp[i][target] = ret
            return ret
        res = target % x
        return min(dfs(2, target - res) + res * 2, dfs(2, target - res + x) + (x - res) * 2) - 1

#
from functools import lru_cache

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        cost = list(range(40))
        cost[0] = 2

        @lru_cache(None)
        def dp(i, targ):
            if targ == 0: return 0
            if targ == 1: return cost[i]
            if i >= 39: return float('inf')

            t, r = divmod(targ, x)
            return min(r * cost[i] + dp(i+1, t),
                       (x-r) * cost[i] + dp(i+1, t+1))

        return dp(0, target) - 1