Broken Calculator: Working Backwards with Greedy Division

You have a calculator with only two buttons: multiply by 2 and subtract 1. Given a startValue and a target, find the minimum number of button presses to reach target from startValue.

This is LeetCode 991: Broken Calculator. It looks like a BFS problem at first glance, but the greedy approach is far simpler and faster.

Example: startValue = 5, target = 8. One optimal path is 5 -> 4 -> 8 (subtract 1, then multiply by 2). That takes 2 operations.

The problem

You start with an integer displayed on the calculator. On each move, you can either:

• Multiply the displayed number by 2
• Subtract 1 from the displayed number

Your goal is to reach target in the fewest moves. Both startValue and target are positive integers up to 10^9.

The brute force approach

The natural instinct is to try BFS from startValue. At each state, branch into two neighbors: value * 2 and value - 1. The first time you reach target, that is your answer.

The problem is that multiplying by 2 can send the value soaring. From startValue = 1 and target = 1000000000, the search space explodes. You would explore values like 2, 4, 8, 16, and then subtract 1 from each of those, creating an exponential tree of states. Even with a visited set, BFS is too slow for inputs in the billions.

The key insight

Instead of going forward from startValue to target, work backward from target to startValue. The reverse operations are:

• If target is even, the last forward operation was multiply by 2, so reverse it: divide by 2.
• If target is odd, the last forward operation was subtract 1, so reverse it: add 1 (which makes it even, and then you can divide).

Working backward, you have exactly one greedy choice at each step. There is no branching. An even number must have come from a doubling, so you divide. An odd number cannot have come from a doubling (doubling always produces an even number), so it must have come from a subtraction, and you add 1.

Once the backward value drops to startValue or below, you stop. If it lands below startValue, the remaining gap is covered by subtract-1 operations in the forward direction (each one costs one move).

Step-by-step walkthrough

Let's trace through startValue = 5, target = 14 and watch the backward algorithm in action.

The forward path corresponding to these 4 operations is: 5 -> 4 -> 8 -> 7 -> 14. You can verify: subtract 1 (to get 4), multiply by 2 (to get 8), subtract 1 (to get 7), multiply by 2 (to get 14). Four operations total.

The code

def brokenCalc(startValue, target):
    ops = 0
    while target > startValue:
        if target % 2 == 1:
            target += 1
        else:
            target //= 2
        ops += 1
    return ops + startValue - target

The while loop runs as long as target is above startValue. Inside, if target is odd, you add 1 to make it even. If it is even, you divide by 2. Each iteration counts as one operation.

When the loop exits, target is at or below startValue. The expression startValue - target accounts for the remaining subtract-1 operations needed in the forward direction. If target equals startValue, that difference is zero and no extra operations are needed.

Complexity analysis

Time is O(log target). Each division by 2 halves the value, and at most one add-1 precedes each division. So the number of loop iterations is at most 2 * log2(target).

Space is O(1). You only track the current value and an operation counter. No queue, no visited set, no recursion stack.

The building blocks

Reverse-direction greedy

When forward operations branch (multiply by 2 creates many possible paths), reversing the problem can eliminate that branching entirely. The reverse operations (divide by 2, add 1) are deterministic: even numbers must be divided, odd numbers must be incremented. This transforms an exponential search into a linear scan.

This pattern shows up whenever one direction of a problem has a unique predecessor for each state. Division by 2 has one result. But multiplication by 2 is just one of many ways to reach a large number, making the forward direction ambiguous.

Even/odd case analysis

The algorithm splits on parity at each step. Even numbers came from doubling, so divide. Odd numbers came from subtracting 1, so add 1. This kind of parity-based decision appears in many number theory problems. The key insight is that multiplying by 2 always produces an even number, so an odd target could never have been the result of a doubling.

Edge cases

• startValue equals target. No operations needed. The loop does not execute, and startValue - target is zero. Return 0.
• startValue is greater than target. You can only subtract 1 (multiplying would take you further away). The answer is simply startValue - target. The loop never runs because target is already at or below startValue.
• target is 1 and startValue is 1. Already equal, return 0.
• Large values (10^9). The greedy approach handles this in about 30 iterations thanks to the logarithmic time complexity. BFS would be impossible at this scale.

From understanding to recall

You just saw how reversing the problem direction collapses an exponential BFS into a simple loop. The entire algorithm fits in six lines: check parity, divide or increment, count operations, and handle the leftover gap when you undershoot startValue.

But knowing the trick and recalling it under pressure are different things. Will you remember to work backward instead of forward? Will you remember that startValue - target handles the gap at the end? Will the even/odd split come to you instantly?

Spaced repetition locks in these patterns. You write the solution from scratch at increasing intervals. After a few rounds, the reverse-direction greedy approach becomes second nature. You stop re-deriving it and start recognizing it on sight.

Related posts

• Reach a Number - Another problem where working with mathematical operations to reach a target benefits from reverse thinking
• Pow(x, n) - Uses the same doubling/halving relationship between multiplication and division
• Integer Replacement - Similar greedy decisions based on whether a number is even or odd