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

Учитывая массив arr[] размера N , представляющий цифры от 0 до 9 , задача состоит в том, чтобы подсчитать количество различных нечетных N -значных целых чисел, которые могут быть сформированы с использованием заданных цифр в массиве.

Примеры:

Input: arr[] = {1, 0, 2, 4}
Output: 4
Explaination: The possible 4-digit odd integers that can be formed using the given digits are 2041, 2401, 4021 and 4201.

Input: arr[] = {2, 3, 4, 1, 2, 3}
Output: 90

Подход: Данная проблема может быть решена с использованием следующих наблюдений:

• Чтобы число было нечетным, его единичный разряд (т. е. 1 ^-я цифра) должен иметь нечетную цифру, т. е. {1, 3, 5, 7, 9}
• Поскольку целое число должно состоять из N цифр, старшая цифра (цифра на N ^-м месте) не может быть равна 0 .
• Все цифры, кроме цифры на 1 ^-м и N ^-м местах, могут иметь любую другую цифру.
• Общее количество способов упорядочить X цифр равно X! / ( freq[0]! * freq[1]! *…* freq[9]! ) , где freq[i] обозначает частоту цифры i в заданных X цифрах.

Для решения задачи следите за количеством нечетных цифр в переменной нечет и количеством цифр, равных 0 в переменной ноль . Итак, в соответствии с приведенными выше наблюдениями, если i представляет N ^-ю цифру, а j представляет 1 ^-ю цифру, переберите все возможные значения i и j и для каждого допустимого (i, j) вычислите количество способов размещения оставшиеся (N-2) цифры.

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

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