LeetCode 991 - Broken Calculator

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 <= X <= 10^9
1 <= Y <= 10^9

X. https://leetcode.com/problems/broken-calculator/discuss/236565/Detailed-Proof-Of-Correctness-Greedy-Algorithm

First, Let use see if the solution exists or not.
Clearly, we can keep doubling x till it goes beyond y. Then we can keep decrementing x till it reaches y. Since the number of operations is not limited, so we conclude that a solution exists.

So now, consider an optimal solution (any solution with the minimal number of steps).
The path is nothing but a sequence of numbers that start at x and end at y.

Assume (x<=y). The other case is trivial

Case 1) Y is odd

Now, consider the last second element of the sequence (optimal path). Recall that we can only move in the sequence via the allowed moves (in the forward direction, we multiply by 2 or decrement by 1). Let us backtrack and see which move did we actually use to get to y. (obviously it has to be one of the two moves).

Now, the move could not have been multiplication by 2, or else y would have been a multiple of 2, which violates our assumption. So the only possible move is the decrement move. It means that the last second term of the sequence is indeed y+1 if y is odd. (And there is no other possibility).

So now we just need to compute the optimal length to reach y+1, and then add 1 to our answer to get the optimal path length for y. (Why? It happens because y+1 lies in an optimal path and any subpath of the optimal path must be optimal or else it would violate our assumptions).

Case 2)Y is even. Say, y=2m

First, let us study the worst case analysis of what is the maximum number that you would touch if you play optimally.

Clearly it is 2*(y-1), since in the worst case, you may end up starting at y-1 and jumping to 2*(y-1) and then coming back. In all other cases, the jump will lead you to a number less than 2*(y-1) and you can easily come back to y one step at a time.

Let us denote 2*(y-1) as jump_max.

Now, If y is even, we cannot say anything about the last second term of the sequence. (The move could be either multiplication or decrement).

However, let us see what happens if the last move was multiplication by 2.

Clearly , the last second element in this case is y/2 = m

So we need to compute the optimal path length to reach m and then we can add 1 to our answer. (But this is valid only if we know that the last move was indeed multiplication.)

What if the last move was decrement?

In that case, the last second element becomes 2m+1, (odd number) , and by the 1st lemma, we conclude that the last third number is 2m+2.

Now 2m+2 is an even number so either a jump happens or it's descendant is 2m+4. So we keep going to the right untill we find ak such that 2m+2k is obtained by jumping from m+k. Clearly such a number exists as the largest number we can encounter is jump_max.

So, now the path looks like

x ....... (m+k) -> 2(m+k) -> (2m+2k-1) -> (2m+2k-2) -> .......y`

But, if you observe carefully, after we reach (m+k) we can decrement k times to reach m and then double to get y. This would cost us (k+1) operations + the cost to reach (m+k). However, the current cost is (1 + 2(m+k) - 2m) = (2k+1) operations + the cost to reach (m+k). Since the new cost is lower, this violates our assumption that the original sequence was an optimal path. Therefore we have a contradiction and we conclude that the last move could not have been decrement.

Conclusion

If y is odd, we know that the last number to be reached before y is (y+1) (in the optimal path)

If y is even, we know that the last number to be reached before y is y/2 (in the optimal path).

So finally we have our recursive relation.

if(x>=y)
cost(x,y) = x-y

if(x< y)
cost (x,y) = 1 + cost(x,y+1) if y is odd
cost (x,y) = 1 + cost(x,y/2) if y is even

Here's the iterative implementation

int brokenCalc(int x, int y)
{
    int count=0;
    while(y!=x)
    {
        if(x>=y) return ((x-y) + count);
        
        /* If y is even, the last move was multiplication, else decrement */
        if(y%2==0) y=y/2 ;
        else y++;
        
        // One operation used
        count ++;
    }
    
    return count;
}

https://leetcode.com/problems/broken-calculator/discuss/234526/Simple-recursive-solution-considering-only-last-bit-(and-proof-why-it's-guranteed-shortest-path)

Trying to prove that the if last bit of Y is 0, the last operation must be doubling:

hypothesis: there can be one or more decrement from Y+1 to Y in the shortest path, where last bit of Y is 0

since last bit of Y+1 is 1, it must be decrement from Y+2(doubling can never make an 1 on last bit)
two options at Y+2.

decrement from Y+3, it's the same as the starting point Y+1 and Y;
doubling from (Y+2)/2, three moves used from (Y+2)/2 to Y: double to Y+2, decrement to Y+1, decrement to Y, while there is a shorter path: decrement to Y/2, double to Y

there we get a contradiction to the hypothesis
so the hypothesis is false
hence, there can be none decrement move(s) from Y+1 to Y in the shortest path if last bit of Y is 0

https://leetcode.com/articles/broken-calculator/
Time Complexity:

O(\log Y)

.
Approach 1: Work Backwards

Instead of multiplying by 2 or subtracting 1 from X, we could divide by 2 (when Y is even) or add 1 to Y.

The motivation for this is that it turns out we always greedily divide by 2:

If say Y is even, then if we perform 2 additions and one division, we could instead perform one division and one addition for less operations [(Y+2) / 2 vs Y/2 + 1].
If say Y is odd, then if we perform 3 additions and one division, we could instead perform 1 addition, 1 division, and 1 addition for less operations [(Y+3) / 2 vs (Y+1) / 2 + 1].

Algorithm

While Y is larger than X, add 1 if it is odd, else divide by 2. After, we need to do X - Y additions to reach X.

public int brokenCalc(int X, int Y) {

int ans = 0;

while (Y > X) {

ans++;

if (Y % 2 == 1)

Y++;

else

Y /= 2;

}

return ans + X - Y;

}

https://leetcode.com/problems/broken-calculator/discuss/234484/JavaC%2B%2BPython-Change-Y-to-X-in-1-Line

Considering how to change Y to X
Opertation 1: Y = Y / 2 if Y is even
Opertation 2: Y = Y + 1

Explanation:

Obviously,
If Y <= X, we won't do Y / 2 anymore.
We will increase Y until it equals to X

So before that, while Y > X, we'll keep reducing Y, until it's smaller than X.
If Y is odd, we can do only Y = Y + 1
If Y is even, if we plus 1 to Y, then Y is odd, we need to plus another 1.
And because (Y + 1 + 1) / 2 = (Y / 2) + 1, 3 operations are more than 2.
We always choose Y / 2 if Y is even.

Why it's right

Actually, what we do is:
If Y is even, Y = Y / 2
If Y is odd, Y = (Y + 1) / 2

We reduce Y with least possible operations, until it's smaller than X.

And we know that, we won't do Y + 1 twice in a row.
Becasue we will always end with an operation Y / 2.

2N times Y + 1 and once Y / 2 needs 2N + 1 operations.
Once Y / 2 first and N times Y + 1 will end up with same result, but needs only N + 1 operations.

Time complexity

We do Y/2 all the way until it's smaller than X,
time complexity is O(log(Y/X)).

for X < Y, if we start from x, then we don't have a clue how should we pick -1 or *2
but if we start from y, and look at it odd-eveness, then we would have a clue
if y is odd, then the last operation must be -1, no other approaches
if y is even, then we have two choices: -1 or * 2.
To get last y from last second y2, we have two ways: y2 * 2 or y2 * 2 - 1 - 1
y2 * 2 -1 - 1 = (y2-1) * 2, and (y2-1) * 2 can save us one operation.
Hence for the last y, we will always pick /2 when it is even

        int res = 0;
        while (Y > X) {
            Y = Y % 2 > 0 ? Y + 1 : Y / 2;
            res++;
        }
        return res + X - Y;

X.
https://leetcode.com/problems/broken-calculator/discuss/234526/Simple-recursive-solution-considering-only-last-bit-(and-proof-why-it's-guranteed-shortest-path)

public int brokenCalc(int X, int Y) {
        if (X>=Y) return X-Y;
        return (Y&1)==0? 1+brokenCalc(X, Y/2):1+brokenCalc(X, Y+1);
        
}

So we check only the last bit of Y, since doubling and -1 can only alter (directly) one bit.

if last bit of Y is 0, the last operation must be doubling, we trace back to Y/2
if last bit of Y is 1, the last operation must be decrement, we trace back to Y+1

Trying to prove that the if last bit of Y is 0, the last operation must be doubling:

hypothesis: there can be one or more decrement from Y+1 to Y in the shortest path, where last bit of Y is 0

since last bit of Y+1 is 1, it must be decrement from Y+2(doubling can never make an 1 on last bit)
two options at Y+2.

decrement from Y+3, it's the same as the starting point Y+1 and Y;
doubling from (Y+2)/2, three moves used from (Y+2)/2 to Y: double to Y+2, decrement to Y+1, decrement to Y, while there is a shorter path: decrement to Y/2, double to Y

there we get a contradiction to the hypothesis
so the hypothesis is false
hence, there can be none decrement move(s) from Y+1 to Y in the shortest path if last bit of Y is 0

https://buptwc.com/2019/02/10/Leetcode-991-Broken-Calculator/

首先我们发现x要么乘2要么减1，如果x初始就比y大，那么只能一直做减法！
在x小于y的情况下：
如果y是奇数，那么最后一个操作一定是减1（显然）
如果y是偶数呢？最后操作一定是乘2吗？答案是yes!

因为对于某个x现在要变为y可能是先乘2再做若干次减法，也可能是先做若干次减法再乘2
第一种用式子表示为1 + 2*x-y，第二种用式子表示为x-y/2 + 1
显然式子2的结果永远小于等于式子1的结果！
所以，我们想要最小化次数一定是先减法再乘2，也就是y为偶数时，最后的操作一定是乘2

那么这里我们就从y开始反推，是奇数就加1，是偶数就除2，一直到y小于等于x为止！

Q: Can we try to change X to Y?
A: Yes we can.

    public int brokenCalc(int X, int Y) {
        int multiple = 1, res = 0;
        while (X * multiple < Y) {
            multiple <<= 1;
            res++;
        }
        int diff = X * multiple - Y;
        while (diff > 0) {  
            res += diff / multiple;
            diff -= diff / multiple * multiple;
            multiple >>= 1;
        }
        return res;
    }

https://gist.github.com/fpdjsns/c4b613504108f095f368c875dbadeda7

    int brokenCalc(int X, int Y) {
        if(X==Y) return 0;
        if(X > Y) return X-Y;
        if(X < Y && Y%2 == 0){
            return 1 + brokenCalc(X, Y/2);  
        } 
        return 1 + brokenCalc(X, Y+1);
    }

http://www.noteanddata.com/leetcode-991-Broken-Calculator-java-solution-note.html

首先数字太大，搜索的方式肯定无论如何优化都不可行，肯定需要构造。

先分情况讨论，如果x>=y, 显然乘以2只会增加步骤，最快的办法一定是直接每次选择减1
然后是x<y的情况，因为题目里面有一个乘以2的操作, 所以我们考虑y和y/2的关系，因为有y/2, 所以还要考虑y是否是偶数，
为了简单一点，我们先从y是偶数开始。
a. x >= y/2
那么, x = (y/2) + d, 也就是d=x-y/2, 并且d>=0,
从x到y的最短路径只有两种可能，一种是先减1到y/2, 然后乘以2到y；还有一种是先乘以2，然后减一到y；
那么，第一种的步骤是step=d+1, 第二种的步骤是step=1+2d, 因为d> 0, 所以第一种步骤最少。

b. x < y/2
对于这种情况，一定是先要到[y/2,y]之间，然后才可能到y，而我们已经知道，从[y/2,y)的最短步骤必须要先到y/2,
那么，问题就可以转化成从x到y/2的最小步骤, 然后最后再加一步乘以2到y就好。
而从x到y/2就是一个递归子问题。
所以，对于偶数的所有情况都有解了。
3. 对于奇数，用同样的方法可以分析，只是最后一步一定是先到y+1, 然后再选择减1操作到y

java题解代码

class Solution {
    public int brokenCalc(int X, int Y) {
        if(X >= Y) {
            return X-Y;    
        }
        else {
            if(Y%2 == 0) {
                if(X >= Y/2) {
                    return (X-Y/2) + 1;        
                }
                else {
                    return brokenCalc(X, Y/2) + 1;
                }
            }
            else { // odd
                if(X >= (Y+1)/2) {
                    return (X-(Y+1)/2) + 2;
                }   
                else {
                    return brokenCalc(X, (Y+1)/2) + 2;
                }
            }
        }
    }
}

分析上面的过程可以发现，从X到Y/2(或者(Y+1)/2)的步骤，其实和递归的操作是一样的，那么代码可以简化一下如下

public int brokenCalc(int X, int Y) {
    if(X >= Y) {
        return X-Y;    
    }
    else {
        return Y%2 == 0 ? (brokenCalc(X, Y/2) + 1) : (brokenCalc(X,(Y+1)/2) + 2);
    }
}