LeetCode 991 - Broken Calculator

LeetCode Problem 991

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

This problem gives us a calculator that starts with an integer startValue and allows only two operations:

1. Multiply the current number by 2
2. Subtract 1

Our goal is to transform startValue into target using the minimum number of operations.

At first glance, this looks like a shortest path problem where we try different sequences of operations until we reach target. However, the challenge is that both startValue and target can be as large as 10^9, which makes brute force exploration infeasible.

To restate the problem in simpler terms, we want to find the fewest button presses needed to convert one integer into another using only doubling and decrementing.

The input consists of two integers:

• startValue, the number initially shown on the calculator.
• target, the desired final number.

The output is a single integer representing the minimum number of operations needed.

The constraints are important here:

• 1 <= startValue, target <= 10^9

Since values can be extremely large, any approach that explores many possible intermediate states will likely be too slow or consume too much memory. We need something significantly more efficient than graph traversal over all reachable numbers.

Several edge cases stand out immediately:

• When startValue >= target, doubling is useless because it only increases the value. The best strategy is simply subtracting 1 repeatedly.
• When target is odd, it cannot result directly from doubling another integer, since doubling always produces even numbers.
• Very large values require an algorithm that avoids simulating unnecessary operations one by one in the forward direction.

Approaches

Brute Force Approach

A natural first idea is to treat this as a shortest path problem. Starting from startValue, we could repeatedly try both possible operations:

• Multiply by 2
• Subtract 1

We can model this as a graph where each number is a node and operations create edges. Since every operation has equal cost, a breadth first search (BFS) would guarantee the minimum number of steps.

The reason this works is that BFS explores states level by level. The first time we encounter target, we know we reached it with the minimum number of operations.

However, this approach becomes impractical for the given constraints. Since numbers can grow large due to repeated doubling, the search space expands rapidly. Even with pruning, BFS may explore an enormous number of states for values near 10^9.

Key Insight for an Optimal Solution

The key observation is that solving the problem backwards is much easier.

Instead of transforming startValue → target, we reverse the operations and think about how to transform target → startValue.

The original operations are:

• Multiply by 2
• Subtract 1

Reversing them gives:

• Divide by 2 (if even)
• Add 1

Now consider what happens when we work backwards:

• If target is even, it must have come from doubling some number. Dividing by 2 is always the best move because it shrinks the value dramatically.
• If target is odd, it could not have been produced by doubling. Therefore, the only way to make progress is to add 1, making it even.

This greedy strategy works because dividing by 2 removes much more distance than repeatedly subtracting 1.

Once target <= startValue, there is no benefit in further reversing operations. We simply subtract the remaining difference.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(target) to exponential in practice	O(target)	BFS over reachable states, too expensive for large values
Optimal	O(log target)	O(1)	Work backwards greedily from target

Algorithm Walkthrough

1. Initialize a counter operations = 0 to track how many moves we make.
2. Continue processing while target > startValue.

We only need greedy reverse operations while the target remains larger than the starting value. 3. If target is odd, increment it by 1.

Since odd numbers cannot result from doubling, the reverse operation must be adding 1. This makes the number even and prepares it for division. 4. If target is even, divide it by 2.

This corresponds to reversing the doubling operation. Dividing by 2 reduces the number much faster than repeatedly decrementing. 5. Increment the operation counter after each transformation. 6. Once target <= startValue, stop the loop.

At this point, the only possible forward operation is subtracting 1, meaning the reverse process simply requires adding the remaining difference. 7. Return:

operations + (startValue - target)

This accounts for the remaining steps needed to bridge the gap.

Why it works

The correctness comes from a greedy invariant.

Whenever target is even, dividing by 2 is always optimal because any alternative sequence involving increments and decrements would take more operations before eventually reaching the same smaller value.

Whenever target is odd, incrementing by 1 is forced because odd numbers cannot come from doubling. There is no alternative optimal move.

Since every step is either forced or provably optimal, the greedy strategy always produces the minimum number of operations.

Python Solution

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        operations = 0

        while target > startValue:
            if target % 2 == 1:
                target += 1
            else:
                target //= 2

            operations += 1

        return operations + (startValue - target)

The implementation directly follows the reverse greedy strategy.

We begin by initializing an operations counter. Then, as long as target remains larger than startValue, we repeatedly shrink it.

Inside the loop, we check whether target is odd or even:

• If odd, we increment it because odd numbers cannot result from doubling.
• If even, we divide by 2 to reverse the doubling operation efficiently.

Each transformation counts as one operation.

Eventually, target becomes less than or equal to startValue. At this stage, the optimal forward solution would simply subtract 1 repeatedly, so we add the difference startValue - target to the answer.

Go Solution

func brokenCalc(startValue int, target int) int {
    operations := 0

    for target > startValue {
        if target%2 == 1 {
            target++
        } else {
            target /= 2
        }

        operations++
    }

    return operations + (startValue - target)
}

The Go implementation mirrors the Python solution closely.

The main difference is syntax. Integer division is naturally handled using /= on integers, which performs floor division automatically in Go. Since all values are within 10^9, integer overflow is not a concern for standard int types on modern LeetCode environments.

No additional data structures are needed, so the implementation remains compact and uses constant extra memory.

Worked Examples

Example 1

Input: startValue = 2, target = 3

We work backwards from 3.

Step	Current Target	Action	Operations
Initial	3	Odd, add 1	0
1	4	Divide by 2	1
2	2	Reached startValue	2

Final answer:

2

Forward interpretation:

2 → 4 → 3

Example 2

Input: startValue = 5, target = 8

Step	Current Target	Action	Operations
Initial	8	Even, divide by 2	0
1	4	Stop, target <= startValue	1

Remaining difference:

5 - 4 = 1

Total:

1 + 1 = 2

Forward interpretation:

5 → 4 → 8

Example 3

Input: startValue = 3, target = 10

Step	Current Target	Action	Operations
Initial	10	Even, divide by 2	0
1	5	Odd, add 1	1
2	6	Even, divide by 2	2
3	3	Reached startValue	3

Final answer:

3

Forward interpretation:

3 → 6 → 5 → 10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log target)	Each division by 2 rapidly reduces the target
Space	O(1)	Only a few variables are used

The time complexity is logarithmic because the target value is repeatedly halved. Although odd numbers occasionally require an increment step, every increment immediately leads to a division, so the total number of operations still scales proportionally to the number of bits in target.

The space complexity is constant because no auxiliary data structures are used.

Test Cases

solution = Solution()

assert solution.brokenCalc(2, 3) == 2  # Example 1
assert solution.brokenCalc(5, 8) == 2  # Example 2
assert solution.brokenCalc(3, 10) == 3  # Example 3

assert solution.brokenCalc(10, 10) == 0  # Same start and target
assert solution.brokenCalc(10, 1) == 9  # startValue > target
assert solution.brokenCalc(1, 1) == 0  # Minimum boundary

assert solution.brokenCalc(1, 1000000000) == 39  # Large target stress test
assert solution.brokenCalc(4, 7) == 2  # Double then decrement
assert solution.brokenCalc(7, 4) == 3  # Only decrements needed
assert solution.brokenCalc(1, 2) == 1  # Single doubling
assert solution.brokenCalc(2, 1) == 1  # Single decrement
assert solution.brokenCalc(8, 17) == 2  # Odd target handling

Test	Why
(2, 3)	Validates example case with odd target
(5, 8)	Validates decrement then doubling path
(3, 10)	Tests mixed operations
(10, 10)	Ensures zero operations when already equal
(10, 1)	Tests startValue > target case
(1, 1)	Minimum boundary values
(1, 1000000000)	Stress test for large input
(4, 7)	Validates reverse odd handling
(7, 4)	Ensures only subtraction is used
(1, 2)	Simple doubling case
(2, 1)	Simple decrement case
(8, 17)	Tests odd target adjustment logic

Edge Cases

When startValue is Already Greater Than target

If startValue >= target, doubling is counterproductive because it only increases the number further away from the goal.

A naive implementation might still attempt unnecessary operations, but the optimal solution immediately recognizes that only subtraction is useful. The answer becomes:

startValue - target

For example:

startValue = 10
target = 4

The optimal path is simply:

10 → 9 → 8 → 7 → 6 → 5 → 4

When target is Odd

Odd targets are tricky because doubling always produces even numbers.

A naive reverse implementation might incorrectly divide odd numbers by 2, producing invalid states. Instead, we must first increment the odd target so it becomes even.

For example:

startValue = 2
target = 7

Reverse process:

7 → 8 → 4 → 2

This ensures correctness.

Very Large Inputs

With values approaching 10^9, brute force approaches become infeasible.

For example:

startValue = 1
target = 1000000000

A forward simulation or BFS would explore far too many possibilities. The greedy reverse solution remains efficient because each division by 2 dramatically shrinks the search space, keeping runtime logarithmic.