Broken Calculator

Broken Calculator

What is this problem about?

You have a "broken" calculator that only has two buttons:

1. Double: Multiplies the number on the screen by 2.
2. Decrement: Subtracts 1 from the number on the screen. Given an initial startValue and a targetValue, find the minimum number of operations to reach the target.

Why is this asked in interviews?

Microsoft and Nutanix use this problem to test your ability to work "backwards" to find an optimal path. While it might look like a Breadth-First Search (BFS) problem, the state space is too large for BFS to be efficient. The problem is a great test of Greedy thinking—specifically, that it's often easier to divide the target by 2 than to multiply the start value.

Algorithmic pattern used

The Greedy pattern is the most effective here, but you apply it from the targetValue back to the startValue.

• If targetValue is even, divide it by 2.
• If targetValue is odd, add 1 to it. Continue this until targetValue is less than or equal to startValue. Finally, the remaining steps are simply the difference between startValue and the current targetValue.

Example explanation

startValue = 2, targetValue = 3 Working backwards from 3:

1. 3 is odd: 3 + 1 = 4. (1 op)
2. 4 is even: 4 / 2 = 2. (1 op)
3. Now target (2) == start (2). Total ops: 2. (Sequence: 2 -> 4 -> 3).

Common mistakes candidates make

The most common mistake is trying to use BFS, which will run out of memory for large target values. Another error is trying to work forward from startValue to targetValue with greedy choices, which is much more difficult to get right. Working backwards simplifies the decision tree significantly.

Interview preparation tip

If a problem involves doubling and subtracting, always try working backwards. Division is a much more restrictive operation than multiplication, which often narrows down the optimal path and makes the greedy choice obvious.