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