Least Operators to Express Number LeetCode solution in C++

1
class Solution {
2
 public:
3
  int leastOpsExpressTarget(int x, int target) {
4
    // base case:
5
    // if target is less then x then we can only have values like either
6
    // x - (x/x)-(x/x).... or (x/x)+(x/x)+(x/x)...
7
    if (target < x) {
8
      return min((x - target) * 2, target * 2 - 1);
9
    }
10

11
    if (x == target) return 0;
12

13
    long long int sum = x;
14
    int ans = 0;
15

16
    // greedly get to the closest number such that x>target and then perform
17
    // either (x/x)+(x/x)+...+(x/x) or
18
    //  x-(x/x)-(x/x)... etc
19

20
    while (sum < target) {
21
      ans++;
22
      sum = sum * x;
23
    }
24

25
    // at this point sum is either greater than target or equal to target
26
    if (sum == target) return ans;
27

28
    // Now we have two choice to reduce the number either we make new number
29
    // ---> target = sum-target (but this can only work if target>sum-target)
30
    // ---> target-sum/x
31
    int op1 = INT_MAX, op2 = INT_MAX;
32
    if (sum - target < target) {
33
      op1 = leastOpsExpressTarget(x, sum - target) + ans;
34
    }
35
    op2 = leastOpsExpressTarget(x, target - sum / x) + ans - 1;
36

37
    return min(op1, op2) + 1;
38
  }
39
};