Skip to main content

991. Broken Calculator

medium

Transform a starting value into a target using only 'double' and 'subtract 1'. The natural DP/BFS forward search explodes; the trick is to work backward from target with a greedy.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

Input
startValue = 2, target = 3
Output
2

Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2

Input
startValue = 5, target = 8
Output
2

Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3

Input
startValue = 3, target = 10
Output
3

Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Forward search (BFS from startValue) explodes — at each step you can multiply or decrement, so the state space is huge.

Hint 2

Work backward from target. The inverse operations are 'divide by 2 (only when target is even)' and 'add 1'. Greedy: prefer divide when possible.

Hint 3

If target is even and target > startValue, divide by 2. If target is odd, add 1 (since divide-by-2 isn't allowed on odd). Once target <= startValue, subtract is the only useful operation forward, costing startValue - target.

Hint 4

Why this greedy is optimal: every 'add 1 going backward' corresponds to a 'subtract 1 going forward'. Each 'divide going backward' is cheaper than the equivalent 'subtract many then double'.

Solution approach

Reveal approach

Work backward from target. Maintain operations = 0. Loop while target > startValue: if target is even, target /= 2; else target += 1. Increment operations each step. Once target <= startValue, add (startValue - target) more operations (the forward 'subtract 1' steps from startValue down to target). Return operations. O(log target) time, O(1) space. The greedy is optimal: every odd target backward MUST add 1 (you can't divide odd by 2 cleanly), and every even target backward should divide (each divide undoes a forward double, which would otherwise be paired with many subtracts).

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • greedy
  • math
  • bfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Broken Calculator and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →