Problem D
Number Game

Lots of Numbers. Photo by Black ice

Sitting outside of MS 4000A, you and your friend both arrived $20$ minutes early to your Math 32B class, and have decided to play some math number games. Your friend proposes the following problem:

Given two numbers $N$ and $M$ such that $M \geq N$, find the minimum number of operations it takes to apply on $N$ to yield $M$. Here, one operation is multiplying a number by $2$, adding $1$ to the number or subtracting $1$ from the number.

Being the computer science major you are, you decide to code up a solution to this problem.


The only line of input contains two integers $N$ and $M$ such that $1 \le N \le 10\, 000$ and $1 \le M \le 20\, 000$.


Print a single integer that represents the minimum number of operations it takes to get from $N$ to $M$.

Sample Explanation

Consider the input $N$ = $2$ and $M$ = $43$, you would have to do $((((((N \times 2) + 1) \times 2) + 1) \times 2) \times 2) - 1$ which is a total of $7$ operations to get to $M$, i.e. $43$.

Sample Input 1 Sample Output 1
2 43
Sample Input 2 Sample Output 2
12 300

Please log in to submit a solution to this problem

Log in