991. Broken Calculator -----------M !!!!!!!!!!

 On a broken calculator that has a number showing on its display, we can perform two operations:

• Double: Multiply the number on the display by 2, or;
• Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

 

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

 

Note:

1. 1 <= X <= 10^9
2. 1 <= Y <= 10^9

A:

下面的这个递归，会有stack overflow.  自己检查下

class Solution {
public:
    int brokenCalc(int X, int Y) {
        unordered_map<int,int> map;
        map[Y] = 0;
        return helper(X, Y, map);
    }
private:
    int helper(int x, int y, unordered_map<int,int> & map){
        if(map.find(x) != map.end())
            return map[x];
        
        int double2 = INT_MAX, sub1 = INT_MAX;
        if(x<y)
            double2 = helper(x+x,y, map);
        if(x>1)
            sub1 = helper(x-1, y, map);
        map[x] = 1+ min(double2, sub1);
        return map[x];
    }
};

-------------官方答案--------------

class Solution {
public:
    int brokenCalc(int X, int Y) {
//         Instead of multiplying by 2 or subtracting 1 from X, we could divide by 2 (when Y is even) or add 1 to Y.
        int ans = 0;
        while(Y >X){
            ans++;
            if( Y % 2 == 1){
                Y++;
            }else{
                Y /= 2;
            }
        }
        return ans + X - Y;
    }
};

Complexity Analysis
Time Complexity: $O(\log Y)$.
Space Complexity: $O(1)$.

If with subtraction and multiplication, the effect of earlier subtraction will be amplified by later multiplications, hence, greedily doing multiplication might not reach optimal solution as an additional early subtraction can have a huge effect.
Whereas with addition and division, earlier addition will be diminished by later divisions. It is thus always better to do division wherever possible.

算法解释