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 thanstartValue
, we can only reach it by performing the reverse operations because multiplyingstartValue
may overshoottarget
. - 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 totarget
. - If
target
is even, the last operation could have been a division by 2, so we divide thetarget
by 2. - We count each operation performed, and once
target
is less than or equal tostartValue
, we stop. - The remaining difference between
startValue
andtarget
represents the number of times we'd need to subtract 1 fromstartValue
to reachtarget
.
By following these steps, we can ensure that we use the minimum operations to transform startValue
into target
on the broken calculator.
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 to0
to count the number of operations needed. - While
startValue
is less thantarget
, a loop continues to perform the reverse operations to bringtarget
closer tostartValue
.- Inside the loop, first, there is a check to see if
target
is odd usingtarget & 1
. This is a bitwise AND operation, which is equivalent to checking if the last bit oftarget
is1
. If it is odd (true
),1
is added totarget
to simulate the reverse of a subtract operation. - If
target
is even (false
), the target is right-shifted by1
bit usingtarget >>= 1
, which is equivalent to dividing the target by2
. - The
ans
counter is then incremented for each operation performed, whether it's an addition or a division.
- Inside the loop, first, there is a check to see if
- When
target
is less than or equal tostartValue
, the loop ends. The final difference betweenstartValue
andtarget
indicates how many subtractions would be necessary if we were working forwards fromstartValue
. Thus,startValue - target
is added to theans
counter to reflect these operations. - Finally,
ans
is returned as the minimum number of operations needed to displaytarget
on the calculator fromstartValue
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 fromtarget
tostartValue
. - Initial
ans
is0
because no operations have been performed yet.
Now we enter the loop:
- First iteration:
target
is8
, which is even.- We perform the reverse of multiplication by dividing by
2
. So,target
=target / 2
=8 / 2
=4
. - Increment
ans
to1
.
- We perform the reverse of multiplication by dividing by
- Second iteration:
target
is4
, which is even.- Again, we divide by
2
. So,target
=target / 2
=4 / 2
=2
. - Increment
ans
to2
.
- Again, we divide by
- Third iteration:
target
is2
, which is even.- Continue with division. So,
target
=target / 2
=2 / 2
=1
. - Increment
ans
to3
.
- Continue with division. So,
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 fromstartValue
.- Add
4
toans
, which is3
from earlier. Nowans
=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
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.
What's the relationship between a tree and a graph?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!