Минимальное количество шагов, необходимых для преобразования A в B

Question

Недавно я участвовал в конкурсе кодеров, где одна из задач была следующей:

Учитывая два целых числа X и Y, найдите минимальное количество шагов, необходимых для преобразования X в Y. Вы можете выполнить следующие операции любое количество раз в любом порядке:

1) Разделите X на любое целое число A, 2) Умножьте X на любое целое число B.

Пример: Если X = 15 и Y = 10 , затем сначала умножьте X на 2, что даст 30, а затем разделите 30 на 3, чтобы получить Y (т. е. 10). Так что минимума нет. шагов в этом случае - 2.

Не знаю, как это решить.

Answer 1

Как указано, минимальное количество шагов не превышает двух: вы всегда можете выбрать A = X и B = Y, чтобы X/A*B = X/X*Y = Y.

Единственное, что вы можете сделать лучше этого, - это следующее:

1. если X% Y = 0, минимальное количество шагов равно 1 и правильный выбор - A = (X / Y).
2. если Y% X = 0 минимальное количество шагов равно 1, и правильный выбор - B = (Y / X).
3. если X = Y, минимальное количество шагов равно 0, так как никакого умножения или деления не требуется.