Минимальное количество заданных операций, необходимое для уменьшения числа до 2

Опубликовано: 22 Сентября, 2022

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

  • Операция 1: Разделите N на 5 , если N точно делится на 5 .
  • Операция 2: вычесть 3 из N .

Если это невозможно, выведите -1 .

Примеры:

Input: N = 28
Output: 3
Explanation: Operation 1: Subtract 3 from 28. Therefore, N becomes 28 – 3 = 25.
Operation 2: Divide 25 by 5. Therefore, N becomes 25 / 5 = 5.
Operation 3: Subtract 3 from 5. Therefore, N becomes 5 – 3 = 2. 
Hence, the minimum number of operations required is 3.

Input: n=10
Output: 1
Explanation: Operation 1: Divide 10 by 5, so n becomes 10/5=2.
Hence, the minimum operations required is 1.

Наивный подход: идея состоит в том, чтобы рекурсивно вычислить минимальное количество необходимых шагов.

  • Если число не делится на 5, то вычесть 3 из n и повторить для измененного значения n, добавив 1 к результату.
  • В противном случае сделайте два рекурсивных вызова, один вычитая 3 из n, а другой опуская n на 5, и возвращайте тот, у которого минимальное количество операций, добавляя 1 к результату.

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

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея заключается в использовании динамического программирования. Выполните следующие действия, чтобы решить эту проблему.

  • Создайте массив, скажем, dp[n+1] для хранения минимальных операций и инициализируйте все записи с помощью INT_MAX, где dp[i] хранит минимальное количество шагов, необходимых для достижения 2 из i .
  • Обработайте базовый случай, инициализировав dp[2] как 0 .
  • Итерировать в диапазоне [2, n], используя переменную i
    • Если значение i*5 ≤ n , то обновите dp[i*5] до минимума dp[i*5] и dp[i]+1 .
    • Если значение i+3 ≤ n , то обновите dp[i+3] до минимума dp[i+3] и dp[i]+1 .
  • Выведите значение dp[n] как результат.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ