Leetcode 1004 Solution

This article provides solution to leetcode question 1004 (least-operators-to-express-number)
Categories:
Tags:
Access this page by simply typing in "lcs 1004" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/least-operators-to-express-number

Solution

from functools import lru_cache

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        m = {}

        @lru_cache(None)
        def dfs(x, target):
            if x == target:
                return 0;
            if x > target:
                return min(
                    2 * target - 1,
                    2 * (x - target),
                )

            s = x
            cnt = 0

            while s < target:
                s *= x
                cnt += 1

            if s == target:
                return cnt

            options = []

            if s - target < target:
                options.append(dfs(x, s - target) + cnt + 1)
            options.append(dfs(x, target - s / x) + cnt)

            return min(options)

        return int(dfs(x, target))