Count of binary strings of length N with even set bit count and at most K consecutive 1s

0 0 9 minutes read

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 n^th position, the number of 1’s remain unchanged. Hence, dp[n][i][s] = dp[n – 1][0][s].
If we place 1 at the n^th 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]$

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 subproblem
int dp[100001][20][2];
 
// Function to calculate
// the possible binary
// strings
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 Code
int 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 approach
import java.io.*;
class GFG{
 
// Table to store solution
// of each subproblem
static int [][][]dp = new int[100001][20][2];
 
// Function to calculate
// the possible binary
// Strings
static 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 Code
public 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 = 3
K = 2
             
print(int(possibleBinaries(N, 0, 0, K)))
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Table to store solution
// of each subproblem
static int [,,]dp = new int[100001, 20, 2];
 
// Function to calculate the
// possible binary Strings
static 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 Code
public 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 subproblem
let 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
// strings
function 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 Code
let N = 3;
let K = 2;
 
// Initialising the
// table with -1
document.write(possibleBinaries(N, 0, 0, K));
 
// This code is contributed by _saurabh_jaiswal
</script>

Output

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
// strings
int 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 Code
int 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
# strings
def 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 Code
N = 3
K = 2
 
# Function call
print(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
// strings
function 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 Code
var N = 3;
var K = 2;
 
// Function call
console.log(possibleBinaries(N, K));
 
// This code is contributed by Tapesh(tapeshdua420)

Output

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 zambiatek!