Подсчет двоичной строки длины N с X 0 и Y 1

Даны положительные целые числа N , X и Y . Задача состоит в том, чтобы найти количество уникальных двоичных строк длины N, содержащих X 0 и Y 1 .

Примеры:

Input: N=5, X=3, Y=2
Output: 10
Explanation: There are 10 binary strings of length 5 with 3 0s and 2 1s, such as: 
00011, 00101, 01001, 10001, 00110, 01010, 10010, 01100, 10100, 11000.

Input: N=3, X=1, Y=2
Output: 3
Explanation: There are 3 binary strings of length 3 with 1 0s and 2 1s, such as: 011, 101, 110

Наивный подход : сгенерируйте все двоичные строки длины N, а затем подсчитайте количество строк с X 0 и Y 1.
Временная сложность: O(2 ^N )
Вспомогательное пространство: O(2 ^N )

Лучший подход : эту проблему также можно решить с помощью комбинаторики. Если длина равна N и задано X 0 с, то будет Y = (N – X) 1 с. Таким образом, мы можем думать об этом как о строке длины N с X 0 и Y 1. Для этого нам нужно найти количество уникальных комбинаций, которые можно получить как _{X}^{N} extrm{C} или _{Y}^{N} extrm{C}. Это можно сделать, используя треугольник Паскаля для вычисления значения комбинации.
Временная сложность: O(N)
Космическая сложность: O(N ² )
Примечание. Этот подход является лучшим, если имеется несколько запросов для X и Y. Тогда он также будет иметь одинаковую сложность времени и пространства.

Подход, оптимизированный по пространству : использование пространства в описанном выше подходе может быть оптимизировано, если мы воспользуемся формулой _{X}^{N} extrm{C} = N!/(X!*(NX)!) и рассчитаем значение с помощью факториала.

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

Временная сложность: O(N)
Вспомогательное пространство: O(1)
Примечание. В случае нескольких (Q) запросов этот подход будет иметь временную сложность O (Q * N).