Минимальное количество шагов, чтобы изменить N на 1, изменив его на 2*N или N/10 на любом шаге

Для заданного целого числа N найдите минимальное количество операций, чтобы изменить N на 1. Если это невозможно, выведите -1. Одна операция определяется либо как преобразование N в число 2*N , либо как преобразование N в число N/10 (только если N делится на 10).

Примеры:

Input: N = 50
Output: 3
Explanation: N can be converted to 1 in 3 steps as follows:
-> Firstly, multiply N by 2 and change N from 50 to 100 (2*N)
-> Then, divide N by 10 and change N from 100 to 10 (N/10)
-> And then, divide N by 10 and change N from 10 to 1 (N/10)

Input: N = 120
Output: -1
Explanation: There is no possible way for Geek to get to position 1.

Подход: N можно преобразовать в 1 , только если N можно свести к 1 либо умножением на 2 , либо делением на 10 на каждом шаге. Теперь N нельзя уменьшить до 1 , следуя этим шагам, если N имеет простой делитель, отличный от 2 и 5 . Более того, если количество двоек больше, чем 5 в простой факторизации N , N не может уменьшить его до 1 , потому что невозможно будет нейтрализовать все двойки . Равное количество двоек и пятерок можно нейтрализовать, разделив число на 10 . Лишние 5 можно нейтрализовать, умножив на лишние 2 , а затем разделив на 10 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные двойки и пятерки как 0 , чтобы подсчитать число 2 и число 5 в простой факторизации числа N.
• Повторяйте цикл while, пока N%2 не станет равным 0 , и выполните следующие шаги:
  • Разделите число N на 2.
  • Увеличьте значение двоек на 1.
• Повторяйте цикл while, пока N%5 не станет равным 0 , и выполните следующие шаги:
  • Разделите число N на 5.
  • Увеличьте значение пятерок на 1.
• Если N равно 1 , а количество двоек меньше, чем равно количеству пятерок, то в качестве ответа выведите 2*пятерки-двойки .
• В противном случае выведите -1.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (log N)
Вспомогательное пространство: O(1)