Количество N-значных чисел, содержащих все однозначные простые числа
Дана натуральное число 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) .
- Верните сумму всех возможных правильных размещений цифр в качестве ответа.
- Если значение индекса равно (N + 1),
- В качестве результата выведите значение, возвращаемое функцией countOfNumbers(1, 0, N) .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * 10 * 2 4 )
Вспомогательное пространство: O(N * 2 4 )