We are given an integer N. We need to count the total number of such binary strings of length N such that the number of ‘0’s in the first string of length N/2 is double of the number of ‘0’s in the second string of length N/2.
Note: N is always an even positive integer.
Examples:
Input : N = 4
Output : 2
Explanation: 0010 and 0001 are two binary string such that the number of zero in the first half is double the number of zero in second half.
Input : N = 6
Output : 9
Naive Approach:We can generate all the binary string of length N and then one by one can check that whether selected string follows the given scenario. But the time complexity for this approach is exponential and is O(N*2N).
Efficient Approach: This approach is based on some mathematical analysis of the problem.
Pre-requisite for this approach: Factorial and Combinatoric with modulo function.
Note: Let n = N/2.
If we perform some analysis step by step:
- The number of strings which contain two ‘0’ in first half string and one ‘0’ in second half string, is equal to nC2 * nC1.
- The number of strings which contain four ‘0’ in first half string and two ‘0’ in second half string, is equal to nC4 * nC2.
- The number of strings which contain six ‘0’ in first half string and three ‘0’ in second half string, is equal to nC6 * nC3.
We repeat above procedure till the number of ‘0’ in first half become n if n is even or (n-1) if n is odd.
So, our final answer is ? (nC(2*i) * nCi), for 2 <= 2*i <= n.
Now, we can compute the required number of strings just by using Permutation and Combination.
Algorithm :
int n = N/2;
for(int i=2;i<=n;i=i+2)
ans += ( nCr(n, i) * nCr(n, i/2);
Note : You can use Dynamic Programming technique to pre-compute CoeFunc(N, i) i.e. nCi.
Time complexity is O(N) if we pre-compute CoeFunc(N, i) in O(N*N).
Implementation:
C++
// CPP for finding number of binary strings// number of '0' in first half is double the// number of '0' in second half of string#include <bits/stdc++.h>// pre define some constant#define mod 1000000007#define max 1001using namespace std;// global values for pre computationlong long int nCr[1003][1003];void preComputeCoeff(){ for (int i = 0; i < max; i++) { for (int j = 0; j <= i; j++) { if (j == 0 || j == i) nCr[i][j] = 1; else nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % mod; } }}// function to print number of required stringlong long int computeStringCount(int N){ int n = N / 2; long long int ans = 0; // calculate answer using proposed algorithm for (int i = 2; i <= n; i += 2) ans = (ans + ((nCr[n][i] * nCr[n][i / 2]) % mod)) % mod; return ans;}// Driver codeint main(){ preComputeCoeff(); int N = 3; cout << computeStringCount(N) << endl; return 0;} |
Java
// Java program for finding number of binary strings// number of '0' in first half is double the// number of '0' in second half of stringclass GFG { // pre define some constant static final long mod = 1000000007; static final long max = 1001; // global values for pre computation static long nCr[][] = new long[1003][1003]; static void preComputeCoeff() { for (int i = 0; i < max; i++) { for (int j = 0; j <= i; j++) { if (j == 0 || j == i) nCr[i][j] = 1; else nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % mod; } } } // function to print number of required string static long computeStringCount(int N) { int n = N / 2; long ans = 0; // calculate answer using proposed algorithm for (int i = 2; i <= n; i += 2) ans = (ans + ((nCr[n][i] * nCr[n][i / 2]) % mod)) % mod; return ans; } // main function public static void main(String[] args) { preComputeCoeff(); int N = 3; System.out.println( computeStringCount(N) ); }}// This code is contributed by Arnab Kundu. |
Python3
# Python3 for finding number of binary strings# number of '0' in first half is double the# number of '0' in second half of string# pre define some constantmod = 1000000007Max = 1001# global values for pre computationnCr = [[0 for _ in range(1003)] for i in range(1003)]def preComputeCoeff(): for i in range(Max): for j in range(i + 1): if (j == 0 or j == i): nCr[i][j] = 1 else: nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % mod # function to print number of required stringdef computeStringCount(N): n = N // 2 ans = 0 # calculate answer using proposed algorithm for i in range(2, n + 1, 2): ans = (ans + ((nCr[n][i] * nCr[n][i // 2]) % mod)) % mod return ans# Driver codepreComputeCoeff()N = 3print(computeStringCount(N))# This code is contributed by mohit kumar |
C#
// C# program for finding number of binary// strings number of '0' in first half is// double the number of '0' in second half// of stringusing System;class GFG { // pre define some constant static long mod = 1000000007; static long max = 1001; // global values for pre computation static long [,]nCr = new long[1003,1003]; static void preComputeCoeff() { for (int i = 0; i < max; i++) { for (int j = 0; j <= i; j++) { if (j == 0 || j == i) nCr[i,j] = 1; else nCr[i,j] = (nCr[i - 1,j - 1] + nCr[i - 1,j]) % mod; } } } // function to print number of required // string static long computeStringCount(int N) { int n = N / 2; long ans = 0; // calculate answer using proposed // algorithm for (int i = 2; i <= n; i += 2) ans = (ans + ((nCr[n,i] * nCr[n,i / 2]) % mod)) % mod; return ans; } // main function public static void Main() { preComputeCoeff(); int N = 3; Console.Write( computeStringCount(N) ); }}// This code is contributed by nitin mittal. |
Javascript
<script>// Javascript for finding number of binary strings// number of '0' in first half is double the// number of '0' in second half of string// pre define some constantvar mod = 1000000007var max = 1001// global values for pre computationvar nCr = Array.from(Array(1003), ()=> Array(1003));function preComputeCoeff(){ for (var i = 0; i < max; i++) { for (var j = 0; j <= i; j++) { if (j == 0 || j == i) nCr[i][j] = 1; else nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % mod; } }}// function to print number of required stringfunction computeStringCount(N){ var n = N / 2; var ans = 0; // calculate answer using proposed algorithm for (var i = 2; i <= n; i += 2) ans = (ans + ((nCr[n][i] * nCr[n][i / 2]) % mod)) % mod; return ans;}// Driver codepreComputeCoeff();var N = 3;document.write( computeStringCount(N));// This code is contributed by noob2000.</script> |
0
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
