Count the number of Binary Strings which have X 1’s and Y 0’s
Given two integers X and Y, the task is to count the number of binary strings which have X 1’s and Y 0’s and there are no two consecutive 1’s in the string.
Examples:
Input: X = 2, Y = 2
Output: 3
Explanation: 1010, 0101, 1001 – these are 3 strings that can be possible such that there are no two consecutive 1’s.Input: X = 5, Y = 3
Output: 0
Explanation: There is no such string that can be possible.
Approach: This can be solved with the following idea:
First calculating factorial of both the given numbers and then calculating power of each one will led us to get the desired answer.
Below are the steps involved:
- Calculating rem Y – X + 1.
- if rem < 0, return 0.
- Calculate the factorial of Y+1 and X by calling ncr function.
- Also, found out the power of both numbers using the binpow function.
- For the answer, multiply the factorial of X with the power of y.
- Then final, multiply answer with power of X.
- Return answer.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> using namespace std; int mod = 1e9 + 7; // Function to calculate power a^b long long binpow( long long a, long long b) { long long ans = 1; while (b) { if (b % 2 == 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b = b / 2; } return ans; } // Function to calculate combinations long long ncr( long long a, long long b) { // Intialising factorial of a, b, c long long facta = 1; long long factb = 1; long long factab = 1; // Iterating for a for ( int i = a; i >= 1; i--) { facta = (facta * i); } // Iterating for b for ( int j = b; j >= 1; j--) { factb = (factb * j); } long long x = (a - b); // Iterating for factorial ab for ( int i = x; i >= 1; i--) { factab = (factab * i); } // calculting power long long invab = binpow(factab, mod - 2); long long invb = binpow(factb, mod - 2); long long answer = (facta * invb) % mod; answer = (answer * invab) % mod; // Return ans return answer; } // Function to count number of strings // that can be constructed int CountString( int x, int y) { // Calculate rem long long rem = y - x + 1; // If rem is negative means no one is there if (rem < 0) { return 0; } // Calculate combinations long long answer = ncr(y + 1, x); // Return answer return answer; } // Driver code int main() { int x = 2; int y = 2; // Function call cout << CountString(x, y); return 0; } |
Java
import java.util.*; public class CountString { static long mod = 1000000007 ; // Function to calculate power a^b static long binpow( long a, long b) { long ans = 1 ; while (b > 0 ) { if (b % 2 == 1 ) { ans = (ans * a) % mod; } a = (a * a) % mod; b /= 2 ; } return ans; } // Function to calculate combinations static long ncr( long a, long b) { // Initializing factorial of a, b, c long facta = 1 ; long factb = 1 ; long factab = 1 ; // Iterating for a for ( long i = a; i >= 1 ; i--) { facta = (facta * i) % mod; } // Iterating for b for ( long j = b; j >= 1 ; j--) { factb = (factb * j) % mod; } long x = a - b; // Iterating for factorial ab for ( long i = x; i >= 1 ; i--) { factab = (factab * i) % mod; } // calculating power long invab = binpow(factab, mod - 2 ); long invb = binpow(factb, mod - 2 ); long answer = (facta * invb) % mod; answer = (answer * invab) % mod; // Return ans return answer; } // Function to count the number of strings that can be constructed static int countString( int x, int y) { // Calculate rem long rem = y - x + 1 ; // If rem is negative means no one is there if (rem < 0 ) { return 0 ; } // Calculate combinations long answer = ncr(y + 1 , x); // Return answer return ( int ) answer; } // Driver code public static void main(String[] args) { int x = 2 ; int y = 2 ; // Function call System.out.println(countString(x, y)); } } |
Python3
# Python Implementation mod = 10 * * 9 + 7 # Function to calculate power a^b def binpow(a, b): ans = 1 while b > 0 : if b % 2 = = 1 : ans = (ans * a) % mod a = (a * a) % mod b = b / / 2 return ans # Function to calculate combinations def ncr(a, b): # Initialize factorial of a, b, and (a-b) facta = 1 factb = 1 factab = 1 # Iterating for a for i in range (a, 0 , - 1 ): facta = (facta * i) # Iterating for b for j in range (b, 0 , - 1 ): factb = (factb * j) x = a - b # Iterating for factorial (a-b) for i in range (x, 0 , - 1 ): factab = (factab * i) # Calculate powers invab = binpow(factab, mod - 2 ) invb = binpow(factb, mod - 2 ) answer = (facta * invb) % mod answer = (answer * invab) % mod # Return the answer return answer # Function to count the number of strings # that can be constructed def CountString(x, y): # Calculate rem rem = y - x + 1 # If rem is negative, no valid strings can be formed if rem < 0 : return 0 # Calculate combinations answer = ncr(y + 1 , x) # Return the answer return answer # Driver code x = 2 y = 2 # Function call print (CountString(x, y)) |
C#
// C# Implementation using System; public class GFG { static int mod = 1000000007; // Function to calculate power a^b static long binpow( long a, long b) { long ans = 1; while (b > 0) { if (b % 2 == 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b = b / 2; } return ans; } // Function to calculate combinations static long ncr( long a, long b) { // Initializing factorial of a, b, c long facta = 1; long factb = 1; long factab = 1; // Iterating for a for ( int i = ( int )a; i >= 1; i--) { facta = (facta * i); } // Iterating for b for ( int j = ( int )b; j >= 1; j--) { factb = (factb * j); } long x = (a - b); // Iterating for factorial ab for ( int i = ( int )x; i >= 1; i--) { factab = (factab * i); } // calculating power long invab = binpow(factab, mod - 2); long invb = binpow(factb, mod - 2); long answer = (facta * invb) % mod; answer = (answer * invab) % mod; // Return answer return answer; } // Function to count the number of strings that can be // constructed static int CountString( int x, int y) { // Calculate rem long rem = y - x + 1; // If rem is negative means no one is there if (rem < 0) { return 0; } // Calculate combinations long answer = ncr(y + 1, x); // Return answer return ( int )answer; } // Driver code static void Main() { int x = 2; int y = 2; // Function call Console.WriteLine(CountString(x, y)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Javascript program for the above approach const mod = BigInt(10**9 + 7); // Function to calculate power a^b function binpow(a, b) { let ans = BigInt(1); while (b > 0n) { if (b % 2n === 1n) { ans = (ans * BigInt(a)) % mod; } a = (BigInt(a) * BigInt(a)) % mod; b = b / 2n; } return ans; } // Function to calculate combinations function ncr(a, b) { // Initialize factorial of a, b, and (a-b) let facta = BigInt(1); let factb = BigInt(1); let factab = BigInt(1); // Iterating for a for (let i = BigInt(a); i >= 1n; i--) { facta = (facta * i) % mod; } // Iterating for b for (let j = BigInt(b); j >= 1n; j--) { factb = (factb * j) % mod; } let x = BigInt(a - b); // Iterating for factorial (a-b) for (let i = x; i >= 1n; i--) { factab = (factab * i) % mod; } // Calculate powers let invab = binpow(factab, mod - 2n); let invb = binpow(factb, mod - 2n); let answer = (facta * invb) % mod; answer = (answer * invab) % mod; // Return the answer return answer; } // Function to count the number of strings that can be constructed function countString(x, y) { // Calculate rem let rem = BigInt(y - x + 1); // If rem is negative, no valid strings can be formed if (rem < 0n) { return 0; } // Calculate combinations let answer = ncr(BigInt(y + 1), BigInt(x)); // Return the answer return Number(answer); } // Driver code const x = 2; const y = 2; // Function call console.log(countString(x, y)); // This code is contributed by Susobhan Akhuli |
Output
3
Time Complexity: O(n*log n)
Auxiliary Space: O(1)