Количество N-значных чисел, содержащих все однозначные простые числа

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

Дана натуральное число N , задача состоит в том, чтобы подсчитать количество N -значных чисел, содержащих все однозначные простые числа.

Примеры:

Input: N = 4
Output: 24
Explanation: The number of single digit primes is 4 i.e.{2, 3, 5, 7}. Hence number of ways to arrange 4 numbers in 4 places is 4! = 24.

Input: N = 5
Output: 936

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные N -значные числа и подсчитать те числа, которые содержат все однозначные простые числа. После проверки всех чисел выведите значение count как результирующее общее количество чисел.

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования, поскольку он имеет перекрывающиеся подзадачи и оптимальную подструктуру. Подзадачи могут быть сохранены в таблице dp[][] с использованием мемоизации, где dp[index][mask] хранит ответ от позиции индекса до конца, где маска используется для хранения количества различных простых чисел, включенных до сих пор. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте глобальный многомерный массив dp[100][1<<4] со всеми значениями как -1 , в котором хранится результат каждого рекурсивного вызова.
  • Индексируйте все однозначные простые числа в порядке возрастания с помощью HashMap .
  • Определите рекурсивную функцию, скажем, countOfNumbers(index, mask, N) , выполнив следующие шаги.
    • Если значение индекса равно (N + 1),
      • Подсчитайте количество различных простых чисел из одной цифры, найдя количество установленных битов в маске.
      • Если count равен 4 , вернуть 1 , так как было сформировано действительное N -значное число.
      • В противном случае вернуть 0 .
    • Если результат состояния dp[index][mask] уже вычислен, верните это значение dp[index][mask] .
    • Если текущий индекс равен 1 , то можно поставить любую цифру из [1-9] , а если N = 1 , то можно поставить и 0 .
    • Для всех остальных индексов можно поставить любую цифру от [0-9] .
    • Если текущая размещенная цифра является простым числом, тогда установите индекс простого числа равным 1 в битовой маске.
    • После корректного размещения рекурсивно вызовите функцию countOfNumbers для (index + 1) .
    • Верните сумму всех возможных правильных размещений цифр в качестве ответа.
  • В качестве результата выведите значение, возвращаемое функцией countOfNumbers(1, 0, N) .

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

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

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