Broken Calculator — Medium Problem & Solution

Problem statement

A calculator on the CodeKairo help desk is half broken: its display starts at startValue and only two keys still work:

• Double — multiply the displayed number by 2.
• Decrement — subtract 1 from the displayed number.

Return the minimum number of key presses needed to show target.

Example 1

Input: startValue = 4, target = 13
Output: 4
Explanation: 4 → 8 → 7 → 14 → 13.

Example 2

Input: startValue = 9, target = 3
Output: 6
Explanation: Six decrements.

Example 3

Input: startValue = 5, target = 32
Output: 4
Explanation: 5 → 4 → 8 → 16 → 32.

Constraints

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

How to solve Broken Calculator

Reverse the process: from target, the inverse moves are "halve" (when even) and "add 1". Halving as early as possible is always best, which gives a simple greedy.

Approach

1. Set ops = 0.
2. While target > startValue: if target is odd, increment it; otherwise halve it. Count each step.
3. Return ops + (startValue - target) — the remaining gap is closed by adding 1 repeatedly (decrements in the forward direction).

Why it works

An odd target can only be reached forwards by a decrement, so backwards it must be +1. For an even target above startValue, halving first is never worse: doing +1 twice and then halving reaches the same number as halving then +1, with one more step. Repeating this exchange turns any optimal reverse sequence into the greedy one without making it longer.

Complexity

• Time — O(log target)
• Space — O(1)

Pitfalls

• Simulating forwards with a BFS explodes for values near 10^9.
• When startValue > target no doubling is useful — the answer is just startValue - target.
• target + 1 stays within 32 bits for target <= 10^9, so no overflow occurs.

Reference solution

Python

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

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Ways to Split Array Into Good Subarrays Medium
• Guess Number Higher or Lower II Medium
• Minimum Cost to Set Cooking Time Medium
• Construct the Longest New String Medium
• Minimum Cost to Make Array Equalindromic Medium
• Minimum Number of Seconds to Make Mountain Height Zero Medium