Broken Calculator - Practice Coding Problems

Broken Calculator - Problem

Math Greedy Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: startValue = 2, target = 3

› Output: 2

💡 Note: Use operations: 2 × 2 = 4, then 4 - 1 = 3. Total: 2 operations

Example 2 — Target Smaller

$ Input: startValue = 5, target = 8

› Output: 2

💡 Note: Use operations: 5 - 1 = 4, then 4 × 2 = 8. Total: 2 operations

Example 3 — Only Subtraction

$ Input: startValue = 3, target = 10

› Output: 3

💡 Note: Working backwards: 10÷2=5, 5+1=6, 6÷2=3. Total: 3 operations

Constraints

1 ≤ startValue, target ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

startValue=2, target=3, operations: ×2, -1

Process

Find minimum operations to reach target

Output

2 operations needed

Key Takeaway

🎯 Key Insight: Working backwards from target with reverse operations is more efficient than exploring all forward paths

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to work backwards from target using reverse operations. The optimal approach is reverse greedy: if target is even divide by 2, if odd add 1. Time: O(log target), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Greedy	O(log target)	O(1)	Work backwards from target using reverse operations for optimal path
BFS (Breadth-First Search)	O(target)	O(target)	Use BFS to explore all possible operations level by level until target is reached

Reverse Greedy — Algorithm Steps

Start from target
If target > startValue and even: divide by 2
If target > startValue and odd: add 1
If target ≤ startValue: subtract to reach startValue

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from target

Begin with target value

Apply reverse operations

If even: ÷2, if odd: +1

Reach start

Continue until we reach or go below startValue

Code -

solution.c — C

#include <stdio.h>

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

int main() {
    int startValue, target;
    scanf("%d", &startValue);
    scanf("%d", &target);
    printf("%d\n", solution(startValue, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log target)

Each division by 2 reduces target by half, leading to logarithmic operations

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few variables, no additional data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler