LeetCode 991: Broken Calculator

Problem Restatement

We are given two integers:

startValue
target

A broken calculator starts by displaying startValue.

It supports only two operations:

We need to return the minimum number of operations needed to display target.

The official constraints are:

Source: LeetCode 991 problem statement.

Input and Output

Function shape:

def brokenCalc(startValue: int, target: int) -> int:
    ...

Examples

Example 1:

startValue = 2
target = 3

One optimal sequence is:

2 -> 4 -> 3

Answer:

2

Example 2:

startValue = 5
target = 8

One optimal sequence is:

5 -> 4 -> 8

Answer:

2

Example 3:

startValue = 3
target = 10

One optimal sequence is:

3 -> 6 -> 5 -> 10

Answer:

3

First Thought: Search Forward

One direct way is to search from startValue.

At every number, we can try:

x * 2
x - 1

Then we search until we reach target.

This resembles BFS, because each operation has cost 1.

But the values can go up to 10^9, so searching through possible values is too large and unnecessary.

Key Insight

Instead of going forward from startValue to target, work backward from target to startValue.

The forward operations are:

Working backward gives a simple greedy rule.

If target is even, divide it by 2.

If target is odd, add 1 to make it even.

Why?

When target is even, dividing by 2 makes the number much smaller in one operation. This reverses a useful double operation.

When target is odd, it cannot be reached by doubling an integer. So the last forward operation must have been decrement. Reversing that means adding 1.

We repeat until target <= startValue.

At that point, going backward further by division is no longer needed. Forward from startValue to this smaller target only requires decrements:

startValue - target

Algorithm

Initialize:

operations = 0

While target > startValue:

1. If target is even:

   target //= 2
2. Otherwise:

   target += 1
3. Increment operations.

After the loop, target <= startValue.

Add the remaining decrement operations:

operations += startValue - target

Return operations.

Correctness

Consider the reverse process from target to startValue.

If the current target is odd and greater than startValue, the previous forward operation could not have been doubling, because doubling always produces an even number. Therefore, the previous forward operation must have been decrement. In reverse, we must add 1.

If the current target is even and greater than startValue, reversing a double operation by dividing by 2 is always optimal. It reduces the value faster than adding 1, and it directly undoes a possible forward double operation.

The algorithm applies these forced or greedy reverse choices until target <= startValue.

Once target <= startValue, the forward process from startValue to target cannot benefit from doubling, because doubling only increases the value. The only needed operation is decrement, repeated startValue - target times.

Thus the algorithm counts the minimum number of operations.

Complexity

Implementation

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

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

            operations += 1

        operations += startValue - target
        return operations

Code Explanation

We count reverse operations:

operations = 0

While the reverse target is still larger than startValue, we reduce it:

while target > startValue:

If target is even, divide by 2:

if target % 2 == 0:
    target //= 2

If target is odd, add 1:

else:
    target += 1

Each reverse operation corresponds to one forward operation:

operations += 1

After the loop, target <= startValue.

The remaining forward operations are simple decrements:

operations += startValue - target

Then return the total:

return operations

Testing

def run_tests():
    s = Solution()

    assert s.brokenCalc(2, 3) == 2
    assert s.brokenCalc(5, 8) == 2
    assert s.brokenCalc(3, 10) == 3
    assert s.brokenCalc(1024, 1) == 1023
    assert s.brokenCalc(1, 1) == 0
    assert s.brokenCalc(1, 1000000000) == 39

    print("all tests passed")

run_tests()