Количество N-значных чисел, имеющих одинаковое количество различных нечетных и четных цифр

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

Примеры:

Input: N = 2
Output : 45
Explanation:
For a 2-digit number, in order to satisfy the condition, the first digit can be even and second digit odd, or the second digit can be odd and first digit even. For the first case there are (4 X 5) = 20 possibilities and for the second case there are (5 X 5) = 25 possibilities. Hence the answer is 45.

Input: N = 3
Output: 135

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

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

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

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

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

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