# Problem statement

There is a broken calculator that has the integer `startValue`

on its display initially. In one operation, you can only either:

- multiply the number on display by
`2`

, or - subtract
`1`

from the number on display.

Given two integers `startValue`

and `target`

, return the minimum number of operations needed to display `target`

on the calculator.

## Example 1

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

## Example 2

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

## Example 3

```
Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.
```

## Constraints

`1 <= x, y <= 10^9`

.

# Solution: Recursive from `target`

It is no doubt that if `startValue >= target`

, you have to go for subtraction exact `startValue - target`

times.

Let us consider only the case `startValue < target`

like the Examples above.
The optimal result of the Examples are:

- Example 1:
`{2 -> 4 -> 3}`

. - Example 2:
`{5 -> 4 -> 8}`

. - Example 3:
`{3 -> 6 -> 5 -> 10}`

.

What is the pattern?

It is hard to see what is the pattern if you read the chains from left to right. Why `2 -> 4`

in Example 1, but `5 -> 4`

in Example 2? Too smart!

What if you read it from right to left?

Here is the pattern:

- If
`target`

is even, its previous value is its half (Example 2, 3). - If
`target`

is odd, its previous value is incremental by one (Example 1).

So you can go backward starting from the `target`

instead of starting from the `startValue`

.

## Code

```
#include <iostream>
int brokenCalc(int startValue, int target) {
if (startValue >= target) {
return startValue - target;
}
if (target % 2 == 0) {
return 1 + brokenCalc(startValue, target/2);
}
return 1 + brokenCalc(startValue, target + 1);
}
int main() {
std::cout << brokenCalc(2,3) << std::endl;
std::cout << brokenCalc(3,10) << std::endl;
std::cout << brokenCalc(5,8) << std::endl;
std::cout << brokenCalc(1024,1) << std::endl;
std::cout << brokenCalc(1,1000000000) << std::endl;
}
```

```
Output:
2
3
2
1023
39
```

## Complexity

- Runtime:
`O(logN)`

, where`N = target`

. - Extra space:
`O(1)`

.

### Did you find this article valuable?

Support **Nhut Nguyen** by becoming a sponsor. Any amount is appreciated!