DEV Community

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on

964. Leetcode Solution in Cpp

class Solution {
 public:
  int leastOpsExpressTarget(int x, int target) {
    return dfs(x, target, {});
  }

 private:
  int dfs(int x, int target, unordered_map<int, int>&& memo) {
    if (memo.count(target))
      return memo[target];
    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 memo[target] = n;

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

Enter fullscreen mode Exit fullscreen mode

Discussion (0)