Уменьшите N до 1 за минимальное количество ходов, либо умножив на 2, либо разделив на 6.

Для заданного целого числа N найдите минимальное количество операций, чтобы уменьшить N до 1 , используя следующие две операции:

• Умножить N на 2
• Разделить N на 6, если N делится на 6

Если N нельзя уменьшить до 1, выведите -1 .

Примеры:

Input: N = 54
Output: 5
Explanation: Perform the following operations–

• Divide N by 6 and get n = 9
• Multiply N by 2 and get n = 18
• Divide N by 6 and get n = 3
• Multiply N by 2 and get n = 6
• Divide N by 6 to get n = 1

Hence, minimum 5 operations needs to be performed to reduce 54 to 1

Input: N = 12
Output: -1

Подход: Задачу можно решить, используя следующие наблюдения.

• Если число состоит из простых чисел, отличных от 2 и 3 , то ответ будет -1 , так как N нельзя уменьшить до 1 с помощью описанных выше операций.
• В противном случае пусть count2 будет количеством двоек в факторизации n, а count3 будет количеством троек в факторизации n .
  • Если count2 > count3, то ответ равен -1 , потому что мы не можем избавиться от всех двоек.
  • В противном случае ответ будет (count3−count2) + count3 .

Ниже приведена реализация вышеуказанного подхода:

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