Nhut Nguyen
Nhut Nguyen

Follow

Nhut Nguyen

Follow
A Solution to Leetcode 991. Broken Calculator

A Solution to Leetcode 991. Broken Calculator

Nhut Nguyen's photo
Nhut Nguyen
·Mar 23, 2022·

2 min read

Play this article

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!

Learn more about Hashnode Sponsors
 
Share this