Formatted question description: https://leetcode.ca/all/991.html

# 991. Broken Calculator

## Level

Medium

## Description

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`

## Solution

It is difficult to figure out how `X`

becomes `Y`

directly, but the problem can be solved in the opposite direction, which is try to make `Y`

become `X`

after some operations. To make `Y`

become `X`

, two operations are allowed. The first operation is half, which is divide `Y`

by 2, which is only allowed when `Y`

is even, and the second operation is increment, which is add 1 to `Y`

, which is allowed for all values of `Y`

.

When `X > Y`

or `Y`

is odd, obviously only increment can be used on `Y`

. When `X < Y`

and `Y`

is even, both half and increment can be used on `Y`

. Obviously using half costs fewer operations than using increment. Even if for the case where `X * 2 > Y`

it is better to use half first, since using half first and increments next costs `1 + X - Y / 2`

operations, and using increments and half first (first increase `Y`

to `X * 2`

then divide `Y`

by 2) costs `X * 2 - Y + 1`

, and obviously `1 + X - Y / 2 < X * 2 - Y + 1`

.

```
class Solution {
public int brokenCalc(int X, int Y) {
int count = 0;
while (X < Y) {
if (Y % 2 == 0)
Y /= 2;
else
Y++;
count++;
}
return count + X - Y;
}
}
```