Solution: Broken Calculator
Tags: javascript, java, python, cpp
Published: 2021-02-21 10:22:17

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/broken-calculator/discuss/1076063).*

---

#### [Leetcode Problem #991 (*Medium*): Broken Calculator](https://leetcode.com/problems/broken-calculator/)

---

#### ***Description:***
</br>
(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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`.

---

#### ***Examples:***

>
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.

---

#### ***Constraints:***
>
 - 1 <= X <= 10^9
 - 1 <= Y <= 10^9

---

#### ***Idea:***
</br>
(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The first thing we should be able to understand is that one of the operations increases **X** while the other one decreases it. So the natural tendency is to think about the solution in terms of applying these operations in order. That is, multiply as many times as you need to before subtracting as many times as you need to.

We see that that's not a viable solution, however, once we recognize that one of the operations is quite obviously multiplicative rather than additive, meaning that a subtraction done *before* a multiplication has twice the impact, for example.

So the trick here is to think of the problem backwards: moving from **Y** to **X** instead of from **X** to **Y**. If **Y** is odd, we're forced to do the additive operation (reversed from the subtractive operation) as we can't divide an odd number by **2** and be able to reach **X**. If **Y** is even, we can prioritize the division operation instead. At each step we can increment our **ans**.

Once **Y** drops below **X**, the remaining difference must be made via the additive operation, so we can just **return** that difference plus **ans**.

**To illustrate why the backwards order leads to the correct solution**, let's take a look at an example: **X = 3, Y = 13**. Under the naive approach discussed at the very beginning of this section, we could apply the multiplication operation **3** times to achieve **24**, then apply the subtraction operation **11** times to bring **Y** back down to **13**.

As we observed before, that **11** is not very efficient, considering that some/all of those subtraction operations could have been done before some/all of the multiplication operations with greater impact.

So what if we had applied as many of those operations as necessary just *before* the last of the three multiplications? Then we would only have needed **5** operations to effect **10** subtraction, plus the leftover **1** to get to **11** at the end.

If we go back one more step before the second of three multiplications, we could have instead done **2** operations then which would have the effect of **8** substraction, plus an extra operation after the second multiplication (adding another **2** subtraction), plus the final operation after all multiplications to reach **11**.

This quickly begins to represent a binary representation of our target difference of **11**:
```js
 Total multiplications:                               In binary: (11 = 1011)
    3    2    1    0
                  11   =   11 in 11 operations                 1011   =   11
              5    1   =   11 in 6 operations               101 + 1   =   6
         2    1    1   =   11 in 4 operations            10 + 1 + 1   =   4
    1    0    1    1   =   11 in 3 operations         1 + 0 + 1 + 1   =   3
```
We can already see that this is starting to look like our backwards approach. At each additional multiplication operation available, we're forced to perform a subtraction operation if the difference is still odd, otherwise, we can divide the remainder by **2** and push it back one multiplication earlier.

Basically, for each multiplication we need to take **X** over **Y**, we take the remaining difference, count the first bit, then shift the difference to the right. And that should sound *exactly* like our backwards approach, because the first bit is a **0** if even and **1** if odd, and shifting to the right is the same as dividing by **2**.

**So why can't we go forwards with X instead of backwards with Y?** As mentioned before, the multiplication operation is, quite obviously, multiplicative, and will have an enhancing effect on any subtraction operations performed before it. Therefore, *we cannot possibly know* how much impact any given subtraction operation will have on the difference between **X** and **Y** until we find out how many multiplication operations we will need after it.

So any solution involving moving **X** to **Y** would at least require "peeking" ahead at part of the solution before progressing with the subtraction operations.

---

#### ***Implementation:***

This solution is almost identical in all four languages.

Python will convert our integer into a float if we simply divide by 2, so we can use the floor division operator instead to maintain the integer.

---

#### ***Javascript Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var brokenCalc = function(X, Y) {
    let ans = 0
    while (X < Y) {
        ans++
        if (Y % 2) Y++
        else Y /= 2
    }
    return X - Y + ans
};
```

---

#### ***Python Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        ans = 0
        while X < Y:
            ans += 1
            if Y % 2: Y += 1
            else: Y //= 2
        return X - Y + ans
```

---

#### ***Java Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int brokenCalc(int X, int Y) {
        int ans = 0;
        while (X < Y) {
            ans++;
            if (Y % 2 > 0) Y++;
            else Y /= 2;
        }
        return X - Y + ans;
    }
}
```

---

#### ***C++ Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (X < Y) {
            ans++;
            if (Y % 2) Y++;
            else Y /= 2;
        }
        return X - Y + ans;
    }
};
```