Skip to content

964. Least Operators to Express Number 👍

  • Time: $O(\log_x \texttt{target})$
  • Space: $O(\log_x \texttt{target})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int leastOpsExpressTarget(int x, int target) {
    return dfs(x, target, {});
  }

 private:
  int dfs(int x, int target, unordered_map<int, int>&& mem) {
    if (const auto it = mem.find(target); it != mem.cend())
      return it->second;
    if (x > target)
      return min(2 * target - 1, 2 * (x - target));
    if (x == target)
      return 0;

    long prod = x;
    int n = 0;
    while (prod < target) {
      prod *= x;
      ++n;
    }
    if (prod == target)
      return mem[target] = n;

    int ans = dfs(x, target - prod / x, std::move(mem)) + n;
    if (prod < 2 * target)
      ans = min(ans, dfs(x, prod - target, std::move(mem)) + n + 1);
    return mem[target] = ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int leastOpsExpressTarget(int x, int target) {
    return dfs(x, target);
  }

  private Map<Integer, Integer> mem = new HashMap<>();

  private int dfs(int x, int target) {
    if (mem.containsKey(target))
      return mem.get(target);
    if (x > target)
      return Math.min(2 * target - 1, 2 * (x - target));
    if (x == target)
      return 0;

    long prod = x;
    int n = 0;
    while (prod < target) {
      prod *= x;
      ++n;
    }
    if (prod == target) {
      mem.put(target, n);
      return mem.get(target);
    }

    int ans = dfs(x, target - (int) (prod / (long) x)) + n;
    if (prod < 2 * target)
      ans = Math.min(ans, dfs(x, (int) (prod - (long) target)) + n + 1);
    mem.put(target, ans);
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def leastOpsExpressTarget(self, x: int, target: int) -> int:
    @functools.lru_cache(None)
    def dfs(target):
      if x > target:
        return min(2 * target - 1, 2 * (x - target))
      if x == target:
        return 0

      prod = x
      n = 0
      while prod < target:
        prod *= x
        n += 1
      if prod == target:
        return n

      ans = dfs(target - prod // x) + n
      if prod < 2 * target:
        ans = min(ans, dfs(prod - target) + n + 1)
      return ans

    return dfs(target)