Broken Calculator solution and explanation
Google
9 more videos on this problem
Broken Calculator | Greedy | Samsung | Leetcode 991codestorywithMIK · 16:24 · 12K views
Broken Calculator | Live Coding with Explanation | Leetcode - 991Algorithms Made Easy · 3:13 · 4K views
Broken Calculator | Leetcode 991 | Math | Day-23Ayushi Sharma · 14:04 · 2K views
Broken Calculator | Leetcode 991 | Maths | Live coding session 🔥🔥Coding Decoded · 10:18 · 2K views
Broken Calculator | Leet code 991 | Theory + Python + JavaSai Anish Malla · 11:42 · 1K views
LeetCode 991. Broken CalculatorHappy Coding · 11:53 · 1K views
Leetcode - Broken Calculator (Python)Timothy H Chang · 4:52 · 803 views
Daily Leetcode #722: Mar 23, 2022 - 991. Broken CalculatorProgramming Live with Larry · 13:09 · 427 views
Daily Leetcode #327: Feb 21, 2021 - 991. Broken CalculatorProgramming Live with Larry · 30:48 · 349 views
991. Broken Calculator | Leetcode Daily Challenge | Medium Level ProblemVishal Rajput · 5:06 · 188 views
The problem
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
1from 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.
def brokenCalc(startValue, target):
operations = 0
while target > startValue:
operations += 1
if target % 2 == 1:
target += 1
else:
target //= 2
return operations + (startValue - target)
startValue = 3
target = 10
print(brokenCalc(startValue, target))public class BrokenCalculator {
public static int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
}
return operations + (startValue - target);
}
public static void main(String[] args) {
int startValue = 3, target = 10;
System.out.println(brokenCalc(startValue, target));
}
}#include <iostream>
using namespace std;
int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
}
return operations + (startValue - target);
}
int main() {
int startValue = 3, target = 10;
cout << brokenCalc(startValue, target) << endl;
return 0;
}function brokenCalc(startValue, target) {
let operations = 0;
while (target > startValue) {
operations++;
if (target % 2 === 1) {
target++;
} else {
target /= 2;
}
}
return operations + (startValue - target);
}
const startValue = 3;
const target = 10;
console.log(brokenCalc(startValue, target));#include <stdio.h>
int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
}
return operations + (startValue - target);
}
int main() {
int startValue = 3, target = 10;
printf("%d\n", brokenCalc(startValue, target));
return 0;
}using System;
class BrokenCalculator {
public static int BrokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
}
return operations + (startValue - target);
}
static void Main() {
int startValue = 3, target = 10;
Console.WriteLine(BrokenCalc(startValue, target));
}
}This Python implementation applies reverse operations to gradually decrease the target below or equal to startValue, adding each operation to the count.
Time Complexity: O(log n), where n is the target.
Space Complexity: O(1).
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.
def brokenCalc(startValue, target):
operations = 0
while target > startValue:
operations += 1
if target % 2 == 1:
target += 1
else:
target //= 2
return operations + (startValue - target)
startValue = 3
target = 10
print(brokenCalc(startValue, target))public class BrokenCalculator {
public static int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
operations++;
}
return operations + (startValue - target);
}
public static void main(String[] args) {
int startValue = 3, target = 10;
System.out.println(brokenCalc(startValue, target));
}
}#include <iostream>
using namespace std;
int brokenCalc(int startValue, int target) {
int operations = 0;
while (startValue < target) {
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
operations++;
}
return operations + (startValue - target);
}
int main() {
int startValue = 3, target = 10;
cout << brokenCalc(startValue, target) << endl;
return 0;
}function brokenCalc(startValue, target) {
let operations = 0;
while (target > startValue) {
if (target % 2 === 1) {
target++;
} else {
target /= 2;
}
operations++;
}
return operations + (startValue - target);
}
const startValue = 3;
const target = 10;
console.log(brokenCalc(startValue, target));#include <stdio.h>
int brokenCalc(int startValue, int target) {
int operations = 0;
while (target != startValue) {
if (target < startValue) {
return operations + (startValue - target);
}
if (target % 2 != 0) {
target++;
} else {
target /= 2;
}
operations++;
}
return operations;
}
int main() {
int startValue = 3, target = 10;
printf("%d\n", brokenCalc(startValue, target));
return 0;
}using System;
class BrokenCalculator {
public static int BrokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
if (target % 2 == 1) {
target++;
} else {
target /= 2;
}
operations++;
}
return operations + (startValue - target);
}
static void Main() {
int startValue = 3, target = 10;
Console.WriteLine(BrokenCalc(startValue, target));
}
}The Python script applies the greedy method to decrementally converge upon the startValue, being efficient with division when possible.
Time Complexity: O(log n), cutting the problem size in half frequently.
Space Complexity: O(1).
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).
function brokenCalc(startValue: number, target: number): number {
let ans = 0;
for (; startValue < target; ++ans) {
if (target & 1) {
++target;
} else {
target >>= 1;
}
}
ans += startValue - target;
return ans;
}func brokenCalc(startValue int, target int) (ans int) {
for startValue < target {
if target&1 == 1 {
target++
} else {
target >>= 1
}
ans++
}
ans += startValue - target
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Operations Approach | Time Complexity: |
| Greedy Approach | Time Complexity: |
| Reverse Calculation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Operations Approach | O(log target) | O(1) | Best general solution. Efficiently reduces the target using reverse operations. |
| Greedy Approach | O(log target) | O(1) | Useful for reasoning about why dividing when even and incrementing when odd gives the optimal path. |
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.