Count of binary string of length N with X 0s and Y 1s

0 0 3 minutes read

Given positive integers N, X and Y. The task is to find the count of unique binary strings of length N having X 0s and Y 1s.

Examples:

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

Naive approach: Generate all binary strings of length N and then count the number of strings with X 0s and Y 1s.
Time Complexity: O(2^N)
Auxiliary Space: O(2^N)

Better Approach: This problem can also be solved using Combinatorics. If the length is N, and given is X 0s, then there will be Y = (N – X) 1s. So we can think of this as a N length string with X 0s and Y 1s. We need to find the number of unique combinations for this, which can be obtained as _{X}^{N}\textrm{C} or _{Y}^{N}\textrm{C}. This can be done using Pascal triangle to calculate the value of combination.
Time Complexity: O(N)
Space Complexity: O(N²)
Note: This approach is the best one if there are multiple queries for X and Y. Then also it will have the same time and space complexity.

Space Optimised Approach: The space consumption in the above approach can be optimised if we take help of the formula _{X}^{N}\textrm{C} = N!/(X!*(N-X)!) and calculate the value by using the factorials.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate factorial
long long int fact(int f)
{
    f++;
    long long int ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
long long int countWays(int N, int X, int Y)
{
    return (fact(N) / (fact(X) * fact(Y)));
}
 
// Driver code
int main()
{
    int N = 5, X = 3, Y = 2;
    cout << countWays(N, X, Y) << endl;
    return 0;
}

Java

// Java program for the above approach
public class GFG{
 
    // Function to calculate factorial
    static int fact(int f)
    {
        f++;
        int ans = 1;
     
        // Loop to calculate factorial of f
        while (--f > 0)
            ans = ans * f;
        return ans;
    }
 
    // Function to calculate combination nCr
    static int countWays(int N, int X, int Y)
    {
        return (fact(N) / (fact(X) * fact(Y)));
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 5, X = 3, Y = 2;
        System.out.println(countWays(N, X, Y));
    }
}
 
// This code is contributed by AnkThon

Python3

# Function to calculate factorial
def fact(f):
  ans = 1;
 
  # Loop to calculate factorial of f
  while (f):
    ans = ans * f;
    f -= 1
 
  return ans;
 
# Function to calculate combination nCr
def countWays(N, X, Y):
  return fact(N) // (fact(X) * fact(Y));
 
 
# Driver code
N = 5
X = 3
Y = 2
print(countWays(N, X, Y))
 
# This code is contributed by gfgking

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate factorial
static int fact(int f)
{
    f++;
    int ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
static int countWays(int N, int X, int Y)
{
    return (fact(N) / (fact(X) * fact(Y)));
}
 
 
// Driver Code
public static void Main()
{
    int N = 5, X = 3, Y = 2;
    Console.Write(countWays(N, X, Y));
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
// Function to calculate factorial
function fact(f) {
  f++;
  let ans = 1;
 
  // Loop to calculate factorial of f
  while (--f > 0)
    ans = ans * f;
  return ans;
}
 
// Function to calculate combination nCr
function countWays(N, X, Y) {
  return Math.floor(fact(N) / (fact(X) * fact(Y)));
}
 
// Driver code
let N = 5, X = 3, Y = 2;
document.write(countWays(N, X, Y))
 
// This code is contributed by saurabh_jaiswal.
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)
Note: In case of multiple(Q) queries this approach will have time complexity O(Q*N).

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!