Минимизируйте операции по уменьшению N до 2 путем многократного уменьшения на 3 или деления на 5.

Для заданного положительного целого числа N задача состоит в том, чтобы найти минимальное количество операций, необходимых для преобразования N в 2 либо путем уменьшения N на 3 , либо путем деления N на 5 , если N делится на 5 . Если уменьшить N до 2 невозможно, то выведите «-1» .

Примеры:

Input: N =10
Output: 1
Explanation:
Following are the operations performed to reduce N to 2:

1. Dividing N by 5, reduces N to 10/5 = 2.

After the above operations, N is reduced to 2. Therefore, the minimum number of operations required is 1.

Input: N = 25
Output: 2

Подход: данная проблема может быть решена с помощью динамического программирования, идея состоит в том, чтобы начать итерацию с 2 и выполнить обе операции в обратном порядке, то есть вместо вычитания выполнить сложение 3 и вместо деления выполнить умножение на 5 в каждое состояние и сохранить минимальное количество операций для каждого возможного значения N в массиве dp[] .

Если значение N достигнуто, то выведите значение dp[N] как минимальное количество операций. В противном случае выведите -1 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте вспомогательный массив, скажем, dp[] размером (N + 1) и инициализируйте все элементы массива с помощью INT_MAX.
• Установите значение dp[2] равным 0 .
• Переберите диапазон [0, N] и обновите значение dp[i] как:
  • дп [я * 5] = мин (дп [я * 5], дп [я] + 1).
  • dp[i + 3] = мин(dp[i + 3], dp[i] + 1).
• Если значение dp[N] равно INT_MAX , выведите -1 . В противном случае выведите результат dp[N] .

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

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