https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/ from Expedia

Thinking process:

1. From the observation, if there’s a number n = b0001?????? (binary representation), the operation will look like below. So, the total operations will be (number of operations of some kind of transformation) + 1 (2nd operation) + minimumOneBitOperations(b0000100000)

b0001??????
b0001100000 <- some kind of transformation
b0000100000 <- 2nd operation
b0000000000 <- same but smaller problem

2. Let’s call “some kind of transformation” as fn2. fn2 apprarently needs n as input, and it also needs to know what’s the target after the transformation. So, fn2 will look like fn2(n, target)
3. Now, how to implement fn2?
4. Let’s say our number is b00110 and our target is b10000. We can do below transfromations. So, the total operations of fn2(b00110, b10000) is: fn2(b0110, b1000) + 1 + minimumOneBitOperations(b1000)

b00110
b01000 <- again fn2, just smaller target
b11000 <- 2nd operation
b10000 <- minimumOneBitOperations with input b1000

5. As you can see, the problem becomes smaller and we re-use the same functions to get the answer (the most import concept of recursion/backtracking)
6. But above case is when number is less than target. How about if our number is greater than target?
7. Say, our number is b10110 and our target is still b10000, which is fn2(b10110, b10000). Now, we basically just need below operations. Then, we get our target. The transformation we make is actually minimumOneBitOperations(b0110)

b10110
b10000 <- just need minimumOneBitOperations(b0110) moves

8. So Now, we have everything. Below is the code

 1class Solution {
 2public:
 3    unordered_map<int, int> dp1;
 4    int leftMost(int n) {
 5        int l = 0;
 6        while ((1<<l)<=n)
 7            l++;
 8        return l-1;
 9    }
10    // equal to minimumOneBitOperations
11    int dfs1(int n) {
12        // base case
13        if (n == 0) return 0;
14        if (n == 1) return 1;
15        // cache result
16        if (dp1.count(n)) return dp1[n];
17        int left = leftMost(n);
18        int ret = 0;
19        // my first point above
20        ret += dfs2(n&((1<<left)-1), 1<<(left-1)); 
21        ret++; 
22        ret += dfs1(1<<(left-1)); 
23        return dp1[n] = ret;
24    }
25    // euqal to fn2
26    int dfs2(int n, int target) {
27        // base case
28        if (n == 0 and target == 1) return 1;
29        if (n == target) return 0;
30        int left = leftMost(target);
31        int ret = 0;
32        if (n < target) { // point #4
33            ret += dfs2(n, 1<<(left-1));
34            ret++;
35            ret += dfs1(1<<(left-1));
36        } else { // point #7
37            ret += dfs1(n&((1<<left)-1));
38        }
39        return ret;
40    }
41    int minimumOneBitOperations(int n) {
42        return dfs1(n);
43    }
44};