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(2N)
Auxiliary Space: O(2N)
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(N2)
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 factoriallong 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 nCrlong long int countWays(int N, int X, int Y){ return (fact(N) / (fact(X) * fact(Y)));}// Driver codeint main(){ int N = 5, X = 3, Y = 2; cout << countWays(N, X, Y) << endl; return 0;} |
Java
// Java program for the above approachpublic 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 factorialdef fact(f): ans = 1; # Loop to calculate factorial of f while (f): ans = ans * f; f -= 1 return ans;# Function to calculate combination nCrdef countWays(N, X, Y): return fact(N) // (fact(X) * fact(Y));# Driver codeN = 5X = 3Y = 2print(countWays(N, X, Y))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate factorialstatic 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 nCrstatic int countWays(int N, int X, int Y){ return (fact(N) / (fact(X) * fact(Y)));}// Driver Codepublic 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 factorialfunction fact(f) { f++; let ans = 1; // Loop to calculate factorial of f while (--f > 0) ans = ans * f; return ans;}// Function to calculate combination nCrfunction countWays(N, X, Y) { return Math.floor(fact(N) / (fact(X) * fact(Y)));}// Driver codelet N = 5, X = 3, Y = 2;document.write(countWays(N, X, Y))// This code is contributed by saurabh_jaiswal.</script> |
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Note: In case of multiple(Q) queries this approach will have time complexity O(Q*N).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
