Minimum number of steps required to convert A to B

user_10859270 0
Viewed 1765

I have recently participated in a coding contest where one of the problems was as follows:

Given two integers X and Y, find the minimum number of steps required to convert X to Y. You can perform the following operations any number of times in any order:

1) Divide X by any integer A, 2)Multiply X by any integer B.

Example: If X=15 and Y=10, then first multiply X by 2 which gives 30 and then divide 30 by 3 to get Y(i.e.,10). So the minimum no. of steps in this case is 2.

I have no idea how to solve it.

data-structures algorithm
1 Answers

As stated, the minimum number of steps is no greater than two: you can always choose A=X and B=Y so that X/A*B = X/X*Y = Y.

The only times you can do better than this are the following:

  1. if X % Y = 0, the minimum number of steps is 1 and the correct choice is A=(X/Y).
  2. if Y % X = 0, the minimum number of steps is 1 and the correct choice is B=(Y/X).
  3. if X = Y, the minimum number of steps is 0 as no multiplications or divisions are required at all.
user_8472690
Related