Broken Calculator

medium greedy math bit manipulation

Problem

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can either multiply the number on the display by 2, or subtract 1 from it. Given two integers startValue and target, return the minimum number of operations needed to display target.

InputstartValue = 2, target = 3

Output2

Use double then decrement: 2 → 4 → 3. That is 2 operations.

startValue

target

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

function brokenCalc(startValue, target) {
  let ops = 0;
  while (target > startValue) {
    if (target % 2 === 0) target /= 2;
    else target += 1;
    ops += 1;
  }
  return ops + (startValue - target);
}

class Solution {
    public int brokenCalc(int startValue, int target) {
        int ops = 0;
        while (target > startValue) {
            if (target % 2 == 0) target /= 2;
            else target += 1;
            ops += 1;
        }
        return ops + (startValue - target);
    }
}

int brokenCalc(int startValue, int target) {
    int ops = 0;
    while (target > startValue) {
        if (target % 2 == 0) target /= 2;
        else target += 1;
        ops += 1;
    }
    return ops + (startValue - target);
}

Explanation

Going forward from startValue is confusing because doubling and subtracting interact in tricky ways. The clever move is to work backward from target instead — and when you reverse the operations they become obvious.

Reversed, "multiply by 2" becomes "divide by 2" and "subtract 1" becomes "add 1". So while target > startValue, if target is even we halve it (the cheapest way to shrink), and if it is odd we add 1 to make it even first. Each of these counts as one operation.

Why greedy works backward: halving shrinks the number much faster than subtracting, so we always want to halve when we can. An odd number cannot be halved cleanly, so the only sensible reverse step is the single +1 that makes it even.

Once target has been reduced to at or below startValue, the only remaining reverse operations are additions of 1, so we add the leftover difference startValue - target as that many more steps.

Example: startValue=2, target=3. 3 is odd, so add 1 → 4 (1 op), then halve → 2 (2 ops). Now it equals start, so the answer is 2.

Time: O(log target) Space: O(1)