Broken Calculator | February Leetcoding Challenge 2021 | Day 21
logo
Manas Sinha
Developer | Designer

By Manas | 21 February 2021

February LeetCoding Challenge 2021

Day 21

BROKEN CALCULATOR

PROBLEM  STATEMENT:
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
strong>Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.
Note:
  • 1 <= X <= 10^9
  • 1 <= Y <= 10^9

Explanation

The first thought that comes to mind is to double X until it becomes greater than the Y and then subtract the excess. But that is not an optimal solution (see example 3 ). Now, if we simply move forward, at every step we can do two things subtract one or multiply two any of which can lead to an optimal solution because as we saw in earlier just multiplying 2 greedily is not optimal. But the problem here is that it can lead to awful lot of paths from X to Y and selecting shortest from them would be very time consuming and obviously we don’t want that 🙂 So instead we move backwards from Y to X because the shortest path from X to Y must be the same if we go Y to X. Doing that we would be bound to increment 1 if the current number is odd, and divide by 2 if it is even. But then you would say dude!! we can increment by 2 if it is an even number and then divide by 2 or increment 3 if its odd and divide by 2. Lets see why we won’t do that:
Say we are at some Y, from here we can
  • If Y is even, then if we perform 2 additions and one division,(Y+2)/2 you will essentially reach Y/2 + 1 So if at the end you wanted to reach Y/2 + 1 why would you use 3 operations if it could have been done in 2, one division and one addition?
  • Example if you are at Y=10
    • [Y+2]/2 = (10+2)/2 = 6 —- > 3 operations
    • Y/2 + 1 = 10/2 + 1 =6 —-> 2 operations
    • choice is yours 😛 (Not really)
  • Same goes for odd number (Y+3)/2 ---> 4 operations is essentially (Y+1)/2 ---> 2 operations.
Going backwards is more deterministic in a sense than going forward so it will give the optimal solution.
ALGORITHM:
  • Decalare a result variable and initialise it with zero.
  • while Y > X increment Y by 1 if Y is odd or divide Y by 2 if Y is even and keep incrementing the result variable.
  • return result + (X-Y)
  • Time complexity : O(LogY)
  • Space complexity : O(1)

code

C++

class Solution {
public:
    
    int brokenCalc(int X, int Y) {
        int ans = 0;
        
        while(Y>X){
            ans += 1;
            if(Y%2) Y+=1;
            else Y /=2;
        }
        return ans + X-Y;
            
    }
};

PYTHON

class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        ans = 0
        
        while Y>X:
            ans += 1
            if Y%2:
                Y += 1
            else:
                Y //= 2
        return ans + (X-Y)

LEAVE A COMMENT

If you like the post leave a comment and share it.

This Post Has One Comment

Leave a Reply