Given two integers N and K, the task is to find the number of binary strings of length N having an even number of 1’s out of which less than K are consecutive.
Examples:
Input: N = 4, K = 2
Output: 4
Explanation:
The possible binary strings are 0000, 0101, 1001, 1010. They all have even number of 1’s with less than 2 of them occurring consecutively.
Input: N = 3, K = 2
Output: 2
Explanation:
The possible binary strings are 000, 101. All other strings that is 001, 010, 011, 100, 110, 111 does not meet the criteria.
Approach:
This problem can be solved by Dynamic Programming.
Let us consider a 3D table dp[][][] to store the solution of each subproblem, such that, dp[n][i][s] denotes the number of binary strings of length n having i consecutive 1’s and sum of 1’s = s. As it is only required to check whether the total number of 1’s is even or not we store s % 2. So, dp[n][i][s] can be calculated as follows:
- If we place 0 at the nth position, the number of 1’s remain unchanged. Hence, dp[n][i][s] = dp[n – 1][0][s].
- If we place 1 at the nth position, dp[n][i][s] = dp[n – 1][i + 1][(s + 1) % 2] .
- From the above two points the recurrence relation formed is given by:
![dp[n][i][s] = dp[n-1][0][s] + dp[n - 1][i + 1][(s + 1)mod 2]](https://neveropen.co.za/wp-content/uploads/2023/10/neveropen_quicklatex.com-8d64d404a7dc1d74596c6bf12bd0bd59_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std;// Table to store solution// of each subproblemint dp[100001][20][2];// Function to calculate// the possible binary// stringsint possibleBinaries(int pos, int ones, int sum, int k){ // If number of ones // is equal to K if (ones == k) return 0; // pos: current position // Base Case: When n // length is traversed if (pos == 0) // sum: count of 1's // Return the count // of 1's obtained return (sum == 0) ? 1 : 0; // If the subproblem has already // been solved if (dp[pos][ones][sum] != -1) // Return the answer return dp[pos][ones][sum]; // Recursive call when current // position is filled with 1 int ret = possibleBinaries(pos - 1, ones + 1, (sum + 1) % 2, k) // Recursive call when current // position is filled with 0 + possibleBinaries(pos - 1, 0, sum, k); // Store the solution // to this subproblem dp[pos][ones][sum] = ret; return dp[pos][ones][sum];}// Driver Codeint main(){ int N = 3; int K = 2; // Initialising the // table with -1 memset(dp, -1, sizeof dp); cout << possibleBinaries(N, 0, 0, K);} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Table to store solution// of each subproblemstatic int [][][]dp = new int[100001][20][2];// Function to calculate// the possible binary// Stringsstatic int possibleBinaries(int pos, int ones, int sum, int k){ // If number of ones // is equal to K if (ones == k) return 0; // pos: current position // Base Case: When n // length is traversed if (pos == 0) // sum: count of 1's // Return the count // of 1's obtained return (sum == 0) ? 1 : 0; // If the subproblem has already // been solved if (dp[pos][ones][sum] != -1) // Return the answer return dp[pos][ones][sum]; // Recursive call when current // position is filled with 1 int ret = possibleBinaries(pos - 1, ones + 1, (sum + 1) % 2, k) + // Recursive call when current // position is filled with 0 possibleBinaries(pos - 1, 0, sum, k); // Store the solution // to this subproblem dp[pos][ones][sum] = ret; return dp[pos][ones][sum];}// Driver Codepublic static void main(String[] args){ int N = 3; int K = 2; // Initialising the // table with -1 for(int i = 0; i < 100001; i++) { for(int j = 0; j < 20; j++) { for(int l = 0; l < 2; l++) dp[i][j][l] = -1; } } System.out.print(possibleBinaries(N, 0, 0, K));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program for the above approach import numpy as np # Table to store solution # of each subproblem dp = np.ones(((100002, 21, 3)))dp = -1 * dp# Function to calculate # the possible binary # strings def possibleBinaries(pos, ones, sum, k): # If number of ones # is equal to K if (ones == k): return 0 # pos: current position # Base Case: When n # length is traversed if (pos == 0): # sum: count of 1's # Return the count # of 1's obtained return 1 if (sum == 0) else 0 # If the subproblem has already # been solved if (dp[pos][ones][sum] != -1): # Return the answer return dp[pos][ones][sum] # Recursive call when current # position is filled with 1 ret = (possibleBinaries(pos - 1, ones + 1, (sum + 1) % 2, k) + # Recursive call when current # position is filled with 0 possibleBinaries(pos - 1, 0, sum, k)) # Store the solution # to this subproblem dp[pos][ones][sum] = ret return dp[pos][ones][sum] # Driver Code N = 3K = 2 print(int(possibleBinaries(N, 0, 0, K)))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Table to store solution// of each subproblemstatic int [,,]dp = new int[100001, 20, 2];// Function to calculate the// possible binary Stringsstatic int possibleBinaries(int pos, int ones, int sum, int k){ // If number of ones // is equal to K if (ones == k) return 0; // pos: current position // Base Case: When n // length is traversed if (pos == 0) // sum: count of 1's // Return the count // of 1's obtained return (sum == 0) ? 1 : 0; // If the subproblem has already // been solved if (dp[pos, ones, sum] != -1) // Return the answer return dp[pos, ones, sum]; // Recursive call when current // position is filled with 1 int ret = possibleBinaries(pos - 1, ones + 1, (sum + 1) % 2, k) + // Recursive call when current // position is filled with 0 possibleBinaries(pos - 1, 0, sum, k); // Store the solution // to this subproblem dp[pos, ones, sum] = ret; return dp[pos, ones, sum];}// Driver Codepublic static void Main(String[] args){ int N = 3; int K = 2; // Initialising the // table with -1 for(int i = 0; i < 100001; i++) { for(int j = 0; j < 20; j++) { for(int l = 0; l < 2; l++) dp[i, j, l] = -1; } } Console.Write(possibleBinaries(N, 0, 0, K));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Table to store solution// of each subproblemlet dp = new Array(100001).fill(-1).map((t) => new Array(20).fill(-1).map((r) => new Array(2).fill(-1)));// Function to calculate// the possible binary// stringsfunction possibleBinaries(pos, ones, sum, k){ // If number of ones // is equal to K if (ones == k) return 0; // pos: current position // Base Case: When n // length is traversed if (pos == 0) // sum: count of 1's // Return the count // of 1's obtained return (sum == 0) ? 1 : 0; // If the subproblem has already // been solved if (dp[pos][ones][sum] != -1) // Return the answer return dp[pos][ones][sum]; // Recursive call when current // position is filled with 1 let ret = possibleBinaries(pos - 1, ones + 1, (sum + 1) % 2, k) // Recursive call when current // position is filled with 0 + possibleBinaries(pos - 1, 0, sum, k); // Store the solution // to this subproblem dp[pos][ones][sum] = ret; return dp[pos][ones][sum];}// Driver Codelet N = 3;let K = 2;// Initialising the// table with -1document.write(possibleBinaries(N, 0, 0, K));// This code is contributed by _saurabh_jaiswal</script> |
Output
2
Time Complexity: O(2*N*K), where N and K represents the given two integers.
Auxiliary Space: O(100001*20*2), no any other extra space is required, so it is a constant.
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a 3D DP table to store the solution of the subproblems.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[N][0][0].
Implementation :
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// the possible binary// stringsint possibleBinaries(int N, int K) { // Table to store solution // of each subproblem int dp[N+1][K+1][2]; memset(dp, 0, sizeof(dp)); // base case for(int i=0; i<=K; i++) { dp[1][i][0] = 1; dp[1][i][1] = 1; } // iterate over subproblems to get the current // value from previous computation for(int i=2; i<=N; i++) { for(int j=0; j<=K; j++) { for(int k=0; k<=1; k++) { if(j == K) { dp[i][j][k] = 0; } else if(k == 0) { dp[i][j][k] = dp[i-1][j+1][1]; } else { dp[i][j][k] = dp[i-1][j+1][0] + dp[i-1][j][1]; } } } } // return final answer return dp[N][0][0];}// Driver Codeint main() { int N = 3; int K = 2; // Function call cout << possibleBinaries(N, K);}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;public class PossibleBinaries { // Function to calculate // the possible binary // strings static int possibleBinaries(int N, int K) { // Table to store solution // of each subproblem int[][][] dp = new int[N+1][K+1][2]; for(int i=0; i<=N; i++) { for(int j=0; j<=K; j++) { Arrays.fill(dp[i][j], 0); } } // base case for(int i=0; i<=K; i++) { dp[1][i][0] = 1; dp[1][i][1] = 1; } // iterate over subproblems to get the current // value from previous computation for(int i=2; i<=N; i++) { for(int j=0; j<=K; j++) { for(int k=0; k<=1; k++) { if(j == K) { dp[i][j][k] = 0; } else if(k == 0) { dp[i][j][k] = dp[i-1][j+1][1]; } else { dp[i][j][k] = dp[i-1][j+1][0] + dp[i-1][j][1]; } } } } // return final answer return dp[N][0][0]; } // Driver Code public static void main(String[] args) { int N = 3; int K = 2; // Function call System.out.println(possibleBinaries(N, K)); }} |
Python3
# Function to calculate# the possible binary# stringsdef possibleBinaries(N, K): # Table to store solution # of each subproblem dp = [[[0 for _ in range(2)] for _ in range(K+1)] for _ in range(N+1)] # base case for i in range(K+1): dp[1][i][0] = 1 dp[1][i][1] = 1 # iterate over subproblems to get the current # value from previous computation for i in range(2, N+1): for j in range(K+1): for k in range(2): if j == K: dp[i][j][k] = 0 elif k == 0: dp[i][j][k] = dp[i-1][j+1][1] else: dp[i][j][k] = dp[i-1][j+1][0] + dp[i-1][j][1] # return final answer return dp[N][0][0]# Driver CodeN = 3K = 2# Function callprint(possibleBinaries(N, K)) |
C#
using System;public class Program { // Function to calculate // the possible binary // strings public static int PossibleBinaries(int N, int K) { // Table to store solution // of each subproblem int[,,] dp = new int[N+1, K+1, 2]; // base case for(int i=0; i<=K; i++) { dp[1, i, 0] = 1; dp[1, i, 1] = 1; } // iterate over subproblems to get the current // value from previous computation for(int i=2; i<=N; i++) { for(int j=0; j<=K; j++) { for(int k=0; k<=1; k++) { if(j == K) { dp[i, j, k] = 0; } else if(k == 0) { dp[i, j, k] = dp[i-1, j+1, 1]; } else { dp[i, j, k] = dp[i-1, j+1, 0] + dp[i-1, j, 1]; } } } } // return final answer return dp[N, 0, 0]; } // Driver Code public static void Main() { int N = 3; int K = 2; // Function call Console.WriteLine(PossibleBinaries(N, K)); }} |
Javascript
// Javascript implementation of given problem// Function to calculate// the possible binary// stringsfunction possibleBinaries(N, K) { // Table to store solution // of each subproblem var dp = new Array(N+1); for (var i = 0; i < dp.length; i++) { dp[i] = new Array(K+1); for (var j = 0; j < dp[i].length; j++) { dp[i][j] = new Array(2); for (var k = 0; k < dp[i][j].length; k++) { dp[i][j][k] = 0; } } } // base case for (var i = 0; i < K+1; i++) { dp[1][i][0] = 1; dp[1][i][1] = 1; } // iterate over subproblems to get the current // value from previous computation for (var i = 2; i < N+1; i++) { for (var j = 0; j < K+1; j++) { for (var k = 0; k < 2; k++) { if (j == K) { dp[i][j][k] = 0; } else if (k == 0) { dp[i][j][k] = dp[i-1][j+1][1]; } else { dp[i][j][k] = dp[i-1][j+1][0] + dp[i-1][j][1]; } } } } // return final answer return dp[N][0][0];}// Driver Codevar N = 3;var K = 2;// Function callconsole.log(possibleBinaries(N, K));// This code is contributed by Tapesh(tapeshdua420) |
Output
2
Time Complexity : O(N*K*2)
Auxiliary Space : O(N*K*2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
