## Optimized Approach(Combinatorics)

The idea is to use combinatorics. If the length of the string is N, and suppose it contains X 0’s, then there will be Y = (N-X) 1’s. To find out the number of distinct binary strings containing X 0’s, it will be equal to ^{N}C_{X.} Now to find all possible binary strings that contain at least X 0’s and at least Y 1’s, we calculate ^{N}C_{i} for all i, where i = [X, N-Y], and it to a variable, let say sum. The value of sum after all iterations will be our required count.

Now the main task is to calculate ^{N}C_{r} efficiently. We will use the pascal triangle to calculate the value of ^{N}C_{r}.

**Pascal’s Triangle **

A Pascal's triangle is a triangular array constructed by summing adjacent elements in preceding rows. Pascal's triangle contains the values of the binomial coefficient.

Source - Coding Ninjas

A pascal’s triangle can be used to find the value of ^{n}C_{r} Since the formula of^{ n}C_{r} = n!/(r! * (n-r)!) it is also the formula for the cell of the pascal’s triangle. So if we create pascal’s triangle, we can get the value of ^{n}C_{r}, in the nth row and rth column.

We will create the pascal’s triable using the conditions:

- The number of ways of selecting 0 elements from the n elements will be 1, i.e.,
^{ n}C_{0} = 1.
- Number of ways of selecting r elements from n elements will be equal to the sum of ways of selecting r-1 elements from n-1 elements and select r elements from n-1 elements, i.e,
^{n}C_{r} = ^{(n-1)}C_{(r-1)} + ^{(n-1)}C_{(r)}.

Now let’s Look at the algorithms for finding the total number of binary strings having at least X 0’s and Y 1’s.

### Steps of Algorithm

- Create the pascal’s triangle of N x N using matrix pas[][].
- Initialize the variable sum = 0 to store the total count of ways of finding the binary strings.
- Start traversing from [X, N-Y] using for loop.
- In each iteration, find the value of pas[N][i], X<=i<=N-Y, and add to the variable sum.
- The calculated sum variable will contain the total number of binary strings with at least X 0’s and Y 1’s.

### Implementation in C++

```
// C++ function to find count of binary string of length N, contains
// at least X 0's and Y 1's.
#include<bits/stdc++.h>
using namespace std;
long long ** pascalsTriangle(long long n){
long long **pas = new long long *[n+1];
for(long long i=0;i<=n;i++){
pas[i] = new long long [n+1];
}
// base condition of the pascal's triangle
pas[0][0] = 1;
pas[1][0] = 1;
pas[1][1] = 1;
for(long long i=2;i<=n;i++){
// selecting 0 element from set of size i
pas[i][0] = 1;
for(long long j=1;j<i;j++){
// condition of pascal's triangle explained above
pas[i][j] = pas[i-1][j] + pas[i-1][j-1];
}
// selecting i element from set of i elements
pas[i][i] = 1;
}
return pas;
}
long long countStrings(long long N, long long X,long long Y){
long long sum = 0;
// calling the pascals triangle function
// to create the pascal's triangle
long long **pas = pascalsTriangle(N);
// staring traversing from X till N-Y, explained above
for(long long i=X;i<=N-Y; i++){
// summation of nCi for all i.
sum += pas[N][i];
}
// contain total number of strings
// having at least X 0’s and Y 1’s.
return sum;
}
// main function
int main(){
long long N = 10, X = 2, Y = 2;
cout << countStrings(N, X, Y) << endl;
}
```

**Output: **

`1002`

#### Complexity Analysis

**Time Complexity: O(NxN)**

Explanation: We are calculating pascal’s triangle, and it’s the size of NxN, so time complexity is O(NxN).

**Space Complexity**: **O(NxN)**

Explanation: We make Pascal’s triangle of size NxN, so its space complexity will be O(NxN).

Also check out - __Substr C++__

## Frequently asked questions

**Q1. What is the Combinatorics? **

**Ans. **Combinatorics is the branch of mathematics concerned with arranging, listing, classifying, constructing, and counting or selecting things.

**Q2. What is the application of pascal's triangle? **

**Ans. **Pascal's triangle is widely used in mathematics and statics; it is used in the probabilistic application, expansion of binomial expression, and the calculation of the combinations.

**Q3. What is the number of substrings of a string of length N? **

**Ans. **The number of substrings of a string of length N is N*(N+1)/2.

## Key takeaways

In this article, we have discussed the problem of finding the count of all binary strings having length N that contains at least X 0’s and Y 1’s. We discussed the naive and optimized approach using combinatorics. We hope you understand the problem and solution properly. Now you can do more similar questions.

**Recommended problems -**

If you are a beginner, interested in coding, and want to learn DSA, you can look for our__ guided path for DSA__, which is free!

Thank you for reading.

Until then, Keep Learning and Keep Coding.