Skip to main content
Talentd

Broken Calculator - Solution & Explanation

MediumMathGreedy13 min readAsked at: Microsoft, Google, Bloomberg +2
Practice this problem

Problem Statement

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

  • 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 <= startValue, target <= 109

Approach Overview

Problem Overview: You start with a number startValue on a calculator. Two operations are allowed: multiply the number by 2 or subtract 1. The task is to reach target using the minimum number of operations. Brute force simulation grows quickly, so the trick is to reason about the operations mathematically instead of exploring every path.

Approach 1: Reverse Operations Approach (O(log target) time, O(1) space)

The key insight is that working backward from target to startValue is far more efficient than building forward. Instead of asking "how do we reach target from startValue?", ask "what value could produce target in one step?" If target is even, the previous state could only be target / 2 (reverse of multiply by 2). If target is odd, the previous step must have been target + 1 (reverse of subtract 1). You repeatedly apply these reverse operations until target becomes less than or equal to startValue. At that point, the only remaining option is subtracting 1 repeatedly, which takes startValue - target operations. Because each division by 2 halves the number, the loop runs roughly O(log target) times. This method relies on simple arithmetic reasoning from math and eliminates unnecessary exploration.

Approach 2: Greedy Approach (O(log target) time, O(1) space)

This problem naturally fits a greedy strategy. The greedy decision is based on making the move that reduces the distance to the target fastest. When working from the target side, dividing by 2 is always the most powerful reduction when the number is even. If the number is odd, division is impossible, so you increment it first to make it even and enable the divide operation in the next step. Each decision locally minimizes the remaining gap between the current value and startValue. Once the target drops below the starting value, greedy logic no longer applies and the only optimal sequence is subtracting 1 repeatedly. This approach is essentially the reasoning layer behind the reverse-operations solution and explains why those specific transformations produce the optimal path.

Recommended for interviews: Interviewers expect the reverse greedy strategy. A naive forward simulation quickly becomes exponential because doubling overshoots the target and creates many possibilities. Demonstrating the reverse thinking shows strong problem-solving ability and comfort with greedy reasoning and mathematical transformations. The final solution runs in O(log target) time with constant space, which is optimal for this problem.

Approach 1: Reverse Operations Approach

Instead of moving from the startValue to target, consider reversing the operations. Start from the target and attempt to reach the startValue. If the target is even, divide it by 2. If it is odd, add 1 to it. Continue until the target is less than or equal to the startValue. This allows you to efficiently compute the minimum steps by potentially making large reductions through division by 2.

This C program uses a loop to apply reverse operations to reduce the target to a value no larger than the startValue. If target is even, it is divided by 2; if odd, it is incremented by 1. Lastly, the remaining difference between startValue and target is added to the operations, as this represents the needed decrements.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n), where n is the target due to halving operation.
Space Complexity: O(1) as no extra space is used.

Try this approach in the editor →

Approach 2: Greedy Approach

Using a greedy approach, always attempt the operation that brings the target closer to the startValue significantly, which is multiplication by 2 in the reverse. Only when all doubling possibilities are exhausted, should we use subtraction/addition operations.

This C solution looks at the current relation between target and startValue, opting to expedite reduction using division when possible, and slow down with addition or subtraction when necessary.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) due to division operations.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Reverse Calculation

We can use a reverse calculation method, starting from target. If target is odd, then target = target + 1, otherwise target = target / 2. We accumulate the number of operations until target leq startValue. The final result is the number of operations plus startValue - target.

The time complexity is O(log n), where n is target. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Reverse Operations Approach

Time Complexity: O(log n), where n is the target due to halving operation.
Space Complexity: O(1) as no extra space is used.

Greedy Approach

Time Complexity: O(log n) due to division operations.
Space Complexity: O(1).

Reverse Calculation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Reverse Operations ApproachO(log target)O(1)Best general solution. Efficiently reduces the target using reverse operations.
Greedy ApproachO(log target)O(1)Useful for reasoning about why dividing when even and incrementing when odd gives the optimal path.

Video Solution

Broken Calculator | Greedy | Samsung | Leetcode 991 • codestorywithMIK • 12,844 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Broken Calculator easy or hard?
Broken Calculator is classified as a medium difficulty problem. The operations themselves are simple, but the key challenge is recognizing that reversing the operations leads to a logarithmic greedy solution.
How to solve Broken Calculator in O(log target)?
Work backward from target. While target is greater than startValue, divide it by 2 if it is even; otherwise add 1 to make it even. Count each operation. Once target becomes less than or equal to startValue, add startValue - target to the operation count.
What is the best approach for Broken Calculator?
The optimal solution is the reverse greedy approach. Instead of building from startValue, reduce the target number. If the target is even, divide it by 2; if it is odd, increment it by 1 to make it even. This strategy minimizes operations and runs in O(log target) time with O(1) space.
What data structure is used in Broken Calculator?
The problem does not require a complex data structure. The solution relies on arithmetic operations and greedy logic using simple integer variables, making it an O(1) space algorithm.
What is the time complexity of Broken Calculator?
The optimal algorithm runs in O(log target) time because each division by 2 significantly reduces the value of target. In the worst case, an odd number requires one extra increment before division, but the total number of iterations still grows logarithmically.
Broken Calculator Python or Java solution available?
Solutions are commonly implemented in Python, Java, C++, C#, and JavaScript. Each implementation follows the same logic: repeatedly transform the target using reverse operations until it reaches the starting value.
Is Broken Calculator asked at Google, Amazon, or Meta?
Broken Calculator is a common medium-level greedy problem similar to questions asked in interviews at companies like Google, Amazon, and Meta. It tests mathematical reasoning, greedy decision making, and the ability to think about reversing operations.

Ready to solve this problem?

Practice Broken Calculator with our built-in code editor and test cases.

Practice on FleetCode
Previous

2 Keys Keyboard

Next

Minimum Operations to Make the Integer Zero