Given a number N, the task is to find the total number of balanced binary strings possible of length N. A binary string is said to be balanced if:
- The number of 0s and 1s are equal in each binary string
- The count of 0s in any prefix of binary strings is always greater than or equal to the count of 1s
- For Example: 01 is a balanced binary string of length 2, but 10 is not.
Example:
Input: N = 4
Output: 2
Explanation: Possible balanced binary strings are: 0101, 0011Input: N = 5
Output: 0
Approach: The given problem can be solved as below:
- If N is odd, then no balanced binary string is possible as the condition of an equal count of 0s and 1s will fail.
- If N is even, then the N length binary string will have N/2 balanced pair of 0s and 1s.
- So, now try to create a formula to get the number of balanced strings when N is even.
So if N = 2, then possible balanced binary string will be “01” only, as “00” and “11” do not have same count of 0s and 1s and “10” does not have count of 0s >= count of 1s in prefix [0, 1).
Similarly, if N=4, then possible balanced binary string will be “0101” and “0011”
For N = 6, then possible balanced binary string will be “010101”, “010011”, “001101”, “000111”, and “001011”
Now, If we consider this series:
For N=0, count(0) = 1
For N=2, count(2) = count(0)*count(0) = 1
For N=4, count(4) = count(0)*count(2) + count(2)*count(0) = 1*1 + 1*1 = 2
For N=6, count(6) = count(0)*count(4) + count(2)*count(2) + count(4)*count(0) = 1*2 + 1*1 + 2*1 = 5
For N=8, count(8) = count(0)*count(6) + count(2)*count(4) + count(4)*count(2) + count(6)*count(0) = 1*5 + 1*2 + 2*1 + 5*1 = 14
.
.
.
For N=N, count(N) = count(0)*count(N-2) + count(2)*count(N-4) + count(4)*count(N-6) + …. + count(N-6)*count(4) + count(N-4)*count(2) + count(N-2)*count(0)
which is nothing but Catalan numbers.
- Hence for any even N return Catalan number for (N/2) as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAXN 500 #define mod 1000000007 // Vector to store catalan number vector<long long int> cat(MAXN + 1, 0); // Function to get the Catalan Number void catalan() { cat[0] = 1; cat[1] = 1; for (int i = 2; i < MAXN + 1; i++) { long long int t = 0; for (int j = 0; j < i; j++) { t += ((cat[j] % mod) * (cat[i - 1 - j] % mod) % mod); } cat[i] = (t % mod); } } int countBalancedStrings(int N) { // If N is odd if (N & 1) { return 0; } // Returning Catalan number // of N/2 as the answer return cat[N / 2]; } // Driver Code int main() { // Precomputing catalan(); int N = 4; cout << countBalancedStrings(N); } |
Java
// Java program for the above approach import java.io.*; class GFG { public static int MAXN = 500; public static int mod = 1000000007; // Vector to store catalan number public static int[] cat = new int[MAXN + 1]; // Function to get the Catalan Number public static void catalan() { cat[0] = 1; cat[1] = 1; for (int i = 2; i < MAXN + 1; i++) { int t = 0; for (int j = 0; j < i; j++) { t += ((cat[j] % mod) * (cat[i - 1 - j] % mod) % mod); } cat[i] = (t % mod); } } public static int countBalancedStrings(int N) { // If N is odd if ((N & 1) > 0) { return 0; } // Returning Catalan number // of N/2 as the answer return cat[N / 2]; } // Driver Code public static void main(String args[]) { // Precomputing catalan(); int N = 4; System.out.println(countBalancedStrings(N)); } } // This code is contributed by saurabh_jaiswal. |
Python3
# Python3 program for the above approach MAXN = 500mod = 1000000007 # Vector to store catalan number cat = [0 for _ in range(MAXN + 1)] # Function to get the Catalan Number def catalan(): global cat cat[0] = 1 cat[1] = 1 for i in range(2, MAXN + 1): t = 0 for j in range(0, i): t += ((cat[j] % mod) * (cat[i - 1 - j] % mod) % mod) cat[i] = (t % mod) def countBalancedStrings(N): # If N is odd if (N & 1): return 0 # Returning Catalan number # of N/2 as the answer return cat[N // 2] # Driver Code if __name__ == "__main__": # Precomputing catalan() N = 4 print(countBalancedStrings(N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { public static int MAXN = 500; public static int mod = 1000000007; // Vector to store catalan number public static int[] cat = new int[MAXN + 1]; // Function to get the Catalan Number public static void catalan() { cat[0] = 1; cat[1] = 1; for (int i = 2; i < MAXN + 1; i++) { int t = 0; for (int j = 0; j < i; j++) { t += ((cat[j] % mod) * (cat[i - 1 - j] % mod) % mod); } cat[i] = (t % mod); } } public static int countBalancedStrings(int N) { // If N is odd if ((N & 1) > 0) { return 0; } // Returning Catalan number // of N/2 as the answer return cat[N / 2]; } // Driver Code public static void Main() { // Precomputing catalan(); int N = 4; Console.Write(countBalancedStrings(N)); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript Program to implement // the above approach let MAXN = 500 let mod = 1000000007 // Vector to store catalan number let cat = new Array(MAXN + 1).fill(0); // Function to get the Catalan Number function catalan() { cat[0] = 1; cat[1] = 1; for (let i = 2; i < MAXN + 1; i++) { let t = 0; for (let j = 0; j < i; j++) { t += ((cat[j] % mod) * (cat[i - 1 - j] % mod) % mod); } cat[i] = (t % mod); } } function countBalancedStrings(N) { // If N is odd if (N & 1) { return 0; } // Returning Catalan number // of N/2 as the answer return cat[(Math.floor(N / 2))]; } // Driver Code // Precomputing catalan(); let N = 4; document.write(countBalancedStrings(N)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
