991. Broken Calculator

Problem Description

In this problem, we are given a "broken" calculator that can perform only two operations:

Multiply the current number displayed by 2.
Subtract 1 from the current number displayed.

The calculator initially shows a number called startValue. The task is to transform this startValue into another given number called target using the fewest number of operations. We need to find out the minimum operations required to achieve this.

Intuition

The intuitive approach to solve this problem might be to start from startValue and try to reach target using a series of multiplications and subtractions. However, this can be very inefficient because the number of possibilities can explode, leading to a high time complexity solution.

Instead, we reverse our thinking process and start from target and try to reach startValue. We take advantage of the fact that the reverse operations (dividing by 2 and adding 1) are more restricted since we can divide by 2 only when the current number is even. This gives us a direction in our decision-making process and reduces the number of choices at each step, making the problem much simpler.

Here's the step-by-step intuition:

If target is greater than startValue, we can only reach it by performing the reverse operations because multiplying startValue may overshoot target.
If target is odd, the last operation performed must have been subtracting 1 (since we cannot divide an odd number by 2). So, we add 1 to target.
If target is even, the last operation could have been a division by 2, so we divide the target by 2.
We count each operation performed, and once target is less than or equal to startValue, we stop.
The remaining difference between startValue and target represents the number of times we'd need to subtract 1 from startValue to reach target.

By following these steps, we can ensure that we use the minimum operations to transform startValue into target on the broken calculator.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Solution Approach

The Solution provided is a direct implementation of the thought process described in the Intuition section. It's a linear approach, where the algorithm goes through a series of steps to transform the target back to the startValue. The crucial insight is that working backward from the target value is more efficient than trying to approach the target starting from the startValue. This is because multiplying can lead to rapidly overshooting the goal, but working backward constrains the choices.

Here's a step-by-step walkthrough of the implementation:

A variable ans is initialized to 0 to count the number of operations needed.
While startValue is less than target, a loop continues to perform the reverse operations to bring target closer to startValue.
- Inside the loop, first, there is a check to see if target is odd using target & 1. This is a bitwise AND operation, which is equivalent to checking if the last bit of target is 1. If it is odd (true), 1 is added to target to simulate the reverse of a subtract operation.
- If target is even (false), the target is right-shifted by 1 bit using target >>= 1, which is equivalent to dividing the target by 2.
- The ans counter is then incremented for each operation performed, whether it's an addition or a division.
When target is less than or equal to startValue, the loop ends. The final difference between startValue and target indicates how many subtractions would be necessary if we were working forwards from startValue. Thus, startValue - target is added to the ans counter to reflect these operations.
Finally, ans is returned as the minimum number of operations needed to display target on the calculator from startValue.

This approach is efficient because each iteration reduces target significantly (either by a factor of 2 or approaching the even number when odd), and there are no unneeded complexities in performing the operations, leading to a time complexity that is linear in terms of the number of operations needed.

By continuously halving the target, we ensure that we're using the most significant reduction at each step when possible, and only when target becomes odd, we perform an addition. This way, despite simulating an inefficient calculator, the algorithm efficiently reaches the optimal solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the broken calculator problem.

Example

startValue = 5
target = 8

Now we need to find the minimum operations to transform startValue into target.

Solution Steps

Since target > startValue, we know we have to work backwards from target to startValue.
Initial ans is 0 because no operations have been performed yet.

Now we enter the loop:

First iteration: target is 8, which is even.
- We perform the reverse of multiplication by dividing by 2. So, target = target / 2 = 8 / 2 = 4.
- Increment ans to 1.
Second iteration: target is 4, which is even.
- Again, we divide by 2. So, target = target / 2 = 4 / 2 = 2.
- Increment ans to 2.
Third iteration: target is 2, which is even.
- Continue with division. So, target = target / 2 = 2 / 2 = 1.
- Increment ans to 3.

The loop ends here because target = 1 is less than startValue = 5. We now add startValue - target to ans.

startValue - target = 5 - 1 = 4. This means we need to perform 4 subtractions if we were moving forwards from startValue.
Add 4 to ans, which is 3 from earlier. Now ans = 3 + 4 = 7.

Conclusion

The minimum number of operations required for the broken calculator starting from 5 to reach 8 is 7. These operations are three divisions (halving the number three times) and four subtractions.

Solution Implementation

1class Solution:
2    def broken_calc(self, start_value: int, target: int) -> int:
3        # Initialize the number of operations to 0
4        operations = 0
5      
6        # Loop until the start value is greater than or equal to target
7        while start_value < target:
8            # If target is odd, increment it to make it even
9            if target % 2:
10                target += 1
11            else:
12                # If target is even, divide it by 2 using right shift
13                target >>= 1
14            # Increment the operations counter
15            operations += 1
16      
17        # Add the difference between start value and the target to the operations
18        # This handles the case where we need to perform 'multiply by 2' operations
19        operations += start_value - target
20      
21        # Return the total number of operations performed
22        return operations
23

1class Solution {
2
3    /**
4     * Calculates the minimum number of operations to transform
5     * startValue to target by either multiplying by 2 or decrementing by 1.
6     * 
7     * @param startValue The starting value.
8     * @param target     The target value.
9     * @return           The minimum number of operations required.
10     */
11    public int brokenCalc(int startValue, int target) {
12        int numOfOperations = 0; // Initialize operation count
13      
14        // Work backwards from the target value until we reach or go below startValue
15        while (startValue < target) {
16            if ((target & 1) == 1) {
17                // If target is odd, increment it (reverse of decrementing in forward direction)
18                target++;
19            } else {
20                // If target is even, halve it (reverse of doubling in forward direction)
21                target >>= 1; // Equivalent to target /= 2;
22            }
23            numOfOperations++; // Increment the count of operations
24        }
25
26        // Once we reach or go below startValue, add the difference
27        // Since at this point only decrements are allowed
28        numOfOperations += startValue - target;
29
30        // Return the total number of operations
31        return numOfOperations;
32    }
33}
34

1class Solution {
2public:
3    // Function to calculate the minimum number of operations required 
4    // to reach from 'startValue' to 'target' by either multiplying by 2 or 
5    // subtracting 1 in each operation.
6    int brokenCalc(int startValue, int target) {
7        int operationCount = 0; // Variable to store the minimum number of operations.
8      
9        // Continue the process until startValue is at least as large as the target.
10        while (startValue < target) {
11          
12            // If the target is an odd number, increment it to make it even.
13            // An odd number cannot be reached by doubling (which always results in an even number),
14            // so we add 1 (which is the reverse operation of subtracting 1).
15            if (target & 1) {
16                target++;
17            }
18            // If the target is even, perform a right bit shift operation equivalent to dividing by 2.
19            // This is the reverse operation of multiplying by 2.
20            else {
21                target >>= 1;
22            }
23
24            // Increase the operation count after each modification to the target.
25            ++operationCount;
26        }
27
28        // Once we have a startValue greater than or equal to the target,
29        // we need to perform (startValue - target) subtractions to reach the target.
30        operationCount += startValue - target;
31
32        // Return the total number of operations required.
33        return operationCount;
34    }
35};
36

1// Global variable to store the minimum number of operations.
2let operationCount = 0;
3
4// Function to calculate the minimum number of operations required
5// to reach from 'startValue' to 'target' by either multiplying by 2 or
6// subtracting 1 in each operation.
7function brokenCalc(startValue: number, target: number): number {
8    // Reset operation count at the start of the function call.
9    operationCount = 0;
10  
11    // Continue the process until 'startValue' is at least as large as the 'target'.
12    while (startValue < target) {
13        // If the 'target' is an odd number, increment it to make it even.
14        // An odd number cannot be reached by doubling (which always results
15        // in an even number), so we add 1 (which is the reverse operation
16        // of subtracting 1 in the problem context).
17        if (target % 2 === 1) {
18            target++;
19        }
20        // If the 'target' is even, divide it by 2.
21        // This is the reverse operation of multiplying by 2.
22        else {
23            target /= 2;
24        }
25
26        // Increase the operation count after each modification to the 'target'.
27        operationCount++;
28    }
29
30    // Once we have a 'startValue' greater than or equal to the 'target',
31    // we need to perform ('startValue' - 'target') subtractions to reach the 'target'.
32    operationCount += startValue - target;
33
34    // Return the total number of operations required.
35    return operationCount;
36}
37

Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(log(target)). The while loop runs until startValue is greater than or equal to target. At each iteration of the loop, if target is even, it is halved (which significantly decreases the target in logarithmic steps), or if it's odd, it is incremented by 1, which eventually makes it even for the next step. Since target is divided by 2 in potentially every other iteration, the loop runs in O(log(target)) time with respect to the target value.

Space Complexity

The space complexity of the code is O(1). The solution does not use any additional storage that grows with the size of the input. It uses a fixed amount of space for the variables ans, startValue, and target irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

991. Broken Calculator

Problem Description

Intuition

Solution Approach

Example Walkthrough

Example

Solution Steps

Conclusion

Solution Implementation

Time and Space Complexity

Time Complexity