(ENG) Algorithm to convert integers each other with minimum number of operations

Question: Convert integer m to integer n with minimum number of operations(m < n). Operations allowed are (-1) and (*2) Eg. 4 and 6.

-1 -> 4 - 1 = 3

*2 -> 3 * 2 = 6

2 operations.

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: Rahul Sharma

ANSWER

Thank you Emre Sermutlu for your feedbacks about the question.

Let's give one more example: 7 and 10

(-1) (-1) and (*2)

One more example: 6 and 10

(-1) and (*2)

We can see that if (m >= n%2), we use (-1) up to (m = n%2), then (*2)

If (m<n%2),...Let's try to see:

ex 1: 3 and 10

(*2) (-1) (5 is half of 10 this can be key!) and (*2)

ex 2: 4 and 10

(-1) we get 3!!!(2.5 =3 is half of 5) Then continue with same way (*2) (-1) and (*2)

ex 3: 1 and 10

(*2) (*2) (-1) we get 3!!!(2.5 =3 is half of 5) Then continue with the same way again!

Why did we try to get 3 every time? What is 3 for these numbers(4 and 10 or 1 and 10)? That is the main question. (2.5 =3 is half of 5; 5 is half of 10)

5

ex 4: 7 and 17

(-1) (-1)(4.5 = 5 is half of 9) (*2) (-1) This time we get 9!(8.5 = 9 is half of 17) (*2) (-1)

ex 5: 4 and 17

(-1)(2.5 = 3 is half of 5) (*2) (-1)(8.5 = 9 is half of 17) (*2) (-1)

Can you understand the regularity? Every time our "secondary" target is half of "main" target. To reach our secondary target, we always use (-1). And whenever our m is smaller than our secondary target, we update our secondary target with its half. However we shouldn't forget our second targets. Because we will use them again. How many secondary targets is there? We can count them in loop with if statement, or we can use dynamic memory allocation ways.

Let's use this way for one more example and see if it works:

ex 6: 11 and 29

11 < (29%2 = 15)

11 > (15%2 = 8)

11 (-1) (-1) (-1) = 8

When we reach our secondary target, then we update m by (*2), and up to our "next" secondary target(if we couldn't reach) we update m by (-1).

8 (*2) (-1) = 15

15 (*2) (-1) = 29