Multiply or Subtract
You are given two numbers - start
s and target t. You’d like to get to the target number t starting from s by only multiplying the current number by 2 or subtracting 1 from it.What would be the minimum number of operations to get from
s to t?Input
The first line of the input contains 2 integers
s and t (1 ≤ s, t ≤ 10 000).Output
The program should print the minimum number of operations to get from
s to t.Examples
Input | Output |
10 1 | 9 |
4 6 | 2 |
Explanation
- Subtract 1 from 10 9 times
- 4 → 3 (subtract 1) → 6 (multiply by 2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB