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 Sam K., 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

More Math practice problems

See all Math problems →