How do you solve Broken Calculator on LeetCode?

Broken Calculator (LeetCode #991) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Understanding the reverse operations can simplify the problem significantly.

What is the brute force solution for Broken Calculator?

The brute force approach for Broken Calculator is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute force approach, we can try every possible sequence of operations starting from the startValue until we reach the target. This means exploring all combinations of multiplying by 2 and subtracting 1, which can be inefficient. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Broken Calculator?

Broken Calculator uses the following concepts: Math, Greedy. The recommended patterns to study are: Greedy, Mathematical Operations.

What are the interview tips for Broken Calculator?

Always think about whether you can reverse the problem for a more efficient solution. Keep track of your operations clearly; it helps in debugging and understanding your logic. Practice similar problems to get comfortable with identifying patterns.

What are common mistakes when solving Broken Calculator?

Not considering the reverse approach, which can lead to more complex solutions. Failing to handle the case when target is less than startValue properly.

#991

Broken Calculator

Medium

MathGreedyGreedyMathematical Operations

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(n)	O(1)

💡

Intuition

Time O(log n)Space O(1)

Instead of starting from startValue and trying to reach target, we can reverse the problem. If we think about how we could have reached target, we can either divide by 2 (if target is even) or add 1 (if target is odd). This allows us to reduce the target towards the startValue efficiently.

⚙️

Algorithm

4 steps

1Step 1: While target is greater than startValue, check if target is even or odd.
2Step 2: If target is even, divide it by 2. If odd, increment it by 1 (to make it even).
3Step 3: Count each operation until target is less than or equal to startValue.
4Step 4: If target is less than startValue, add the difference to the operation count.

solution.py11 lines

1# Full working Python code
2
3def brokenCalculator(startValue, target):
4    operations = 0
5    while target > startValue:
6        if target % 2 == 0:
7            target //= 2
8        else:
9            target += 1
10        operations += 1
11    return operations + (startValue - target)

ℹ

Complexity note: The time complexity is O(log n) because we are halving the target value in each step when it is even, which significantly reduces the number of operations needed.

1Understanding the reverse operations can simplify the problem significantly.
2Dividing by 2 is a powerful operation that reduces the problem size quickly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.