Broken Calculator - Leetcode Solution

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:

Input: X = 1024, Y = 1 Output: 1023 Explanation: Use decrement operations 1023 times.

Approach:

The approach to solve this problem is by performing backwards operations. Instead of starting from X and going towards Y, we start from Y and go towards X.

We will perform the decrement operation if Y is odd (as we cannot reach to an odd number by multiplication with 2 only) and divide Y by 2 for all other cases (as multiplying by 2 is more efficient than subtracting by 1).

We will continue this process until Y becomes equal to X. The number of steps taken in the process will be the result.

Algorithm:

If X is greater than or equal to Y, we can simply return X-Y (subtract 1 repeatedly until we reach X).

Initialize a count variable to 0.

Perform the following operations until Y becomes equal to X.

If Y is odd, decrement it and increment the count variable.

Otherwise, divide Y by 2 and increment the count variable.

After the while loop, return the count variable.

Time Complexity:

The time complexity of the above algorithm is O(log(Y)), as we are performing operations on Y in every iteration, and in each iteration we are dividing Y by 2 (which reduces the number by half, on average). Since we are looping until Y becomes equal to X, the maximum number of iterations required is log(Y) (base 2), giving us the time complexity of O(log(Y)).

Space Complexity:

The space complexity of the above algorithm is O(1), as we are not using any additional data structures to solve this problem - only a constant number of variables are required.

Code:

class Solution: def brokenCalc(self, X: int, Y: int) -> int:

    #if X is greater than or equal to Y, return the difference between them
    if X >= Y:
        return X-Y

    count = 0
    
    while Y != X:
        #if Y is odd, decrement it and increment the count variable
        if Y % 2:
            Y += 1
        #otherwise, divide Y by 2 and increment the count variable
        else:
            Y //= 2
        count += 1

    return count

Conclusion:

This problem can be solved efficiently using the above approach. By focusing on the end result (Y) and working backwards, we can avoid having to try all possible sequences of operations.

1