Problem
A broken calculator can only do two operations: +1 (add one) or ×2 (multiply by two).
Starting from number A, what is the minimum number of operations to reach exactly B?
Starting from number A, what is the minimum number of operations to reach exactly B?
🧠 DP Concept
Trick: work backwards from B to A!
Use a while loop. While current > A:
— If current is even and current/2 ≥ A → divide by 2 (undo a ×2)
— Otherwise → subtract 1 (undo a +1)
— Count each step.
Why backwards? Going forward, you don't know when to +1 vs ×2. Going backward, the choice is clear: if even, dividing is almost always better.
Use a while loop. While current > A:
— If current is even and current/2 ≥ A → divide by 2 (undo a ×2)
— Otherwise → subtract 1 (undo a +1)
— Count each step.
Why backwards? Going forward, you don't know when to +1 vs ×2. Going backward, the choice is clear: if even, dividing is almost always better.
Input Variables (pre-loaded)
💡 This problem uses a while loop and variables — no dp[] table needed! Use the divisible by check from Logic.
Your Output
Result
—
Run your program to see the result.
Execution Log
Ready. Press ▶ Run to start.
Expected Answer
Answer:
?
Hint
Step 0