Double or Decrement

Medium

An old calculator has only two working keys: one doubles the number on the display, the other subtracts one from it. The display currently shows start. Return the smallest number of key presses after which the display shows goal.

Example 1

start=3, goal=5 → 2

3 → 6 (double) → 5 (minus one): two presses.

Example 2

start=6, goal=10 → 2

It pays to decrement first: 6 → 5 → 10. Two presses.

Example 3

start=9, goal=4 → 5

The number already exceeds the goal and doubling only hurts: press minus one five times.

Constraints

1 ≤ start ≤ 10⁹
1 ≤ goal ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Math

Similar problems

Smallest Number From Digit Factors Medium One Digit Swap Medium Largest Number With Non-Decreasing Digits Medium Fewest Guests by Lanyard Color Medium Up or Down for Every Post Medium

Input

start=3, goal=5

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.