Follow

Follow

Nhut Nguyen
Â·Mar 23, 2022Â·

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