Количество способов составить 2 ожерелья из N бусин, содержащих N/2 бусин в каждой

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

Примеры:

Input: N = 2
Output: 1
Explanation: 
The only possible way to make two necklaces is that {1 | 2}.

Input: N = 4
Output: 3
Explanation: 
The possible ways to make two necklaces are {(1, 2) | (3, 4)}, {(1, 3) | (2, 4)}, and {(1, 4) | (2, 3)}.

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

• Определите функцию, скажем, factorial для вычисления факториала числа, выполнив следующие шаги:
  • Базовый случай: если n = 0 , верните 1 .
  • Если n != 0 , то рекурсивно вызовите функцию и верните n * factorial(n-1) .
• Инициализируйте переменную, скажем , как C(N, N/2), то есть количество способов выбрать N/2 бусин из N бусин.
• Поскольку ожерелье круглое, количество способов перестановки N/2 бусин является факториальным (N/2-1), поэтому умножьте значение ans на факториал (N/2-1) * факториал (N/2-1) . так как есть два ожерелья.
• Теперь разделите ответы на 2. Из-за симметричного распределения. Например, для N=2 распределение {1 | 2} и {2 | 1} считаются одинаковыми.
• Наконец, после выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

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