Подсчитайте N-значные числа, состоящие из четных и простых цифр на нечетных и четных позициях соответственно.
Для данного положительного целого числа N задача состоит в том, чтобы найти количество целых чисел из N цифр , имеющих четные цифры в нечетных индексах и простые цифры в четных индексах.
Примеры:
Input: N = 2
Output: 20
Explanation:
Following are the possible number of 2-digits satisfying the given criteria {20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 50, 52, 54, 56, 58, 70, 72, 74, 76, 78}. Therefore, the count of such number is 20.Input: N = 5
Output: 1600
Подход: Данную проблему можно решить, используя концепцию перестановок и комбинаций, заметив тот факт, что существует только 4 варианта выбора для четных позиций как [2, 3, 5, 7] и 5 вариантов для нечетных позиций как [0, 2, 4, 6, 8] . Следовательно, количество N-значных чисел, удовлетворяющих заданным критериям, определяется выражением:
total count = 4P5Q, where P and Q is the number of even and odd positions respectively.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (log N)
Вспомогательное пространство: O(1)