Count of binary strings of length N with even set bit count and at most K consecutive 1s
Last Updated :
06 Jul, 2023
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]
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 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 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# 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
<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>
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
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));
}
}
# 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))
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 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)
Time Complexity : O(N*K*2)
Auxiliary Space : O(N*K*2)
Similar Reads
Count of Binary Strings of length at most N with set bit count as multiple of K
Given two integers N and K, the task is to find the count of binary strings of at most N length that can be formed such that the count of consecutive 1's is always a multiple of K. Example: Input: N = 3, K = 2Output: 6Explanation: Binary strings of atmost N length containing consecutive 1's as a mul
7 min read
Count possible binary strings of length N without P consecutive 0s and Q consecutive 1s
Given three integers N, P, and Q, the task is to count all possible distinct binary strings of length N such that each binary string does not contain P times consecutive 0’s and Q times consecutive 1's. Examples: Input: N = 5, P = 2, Q = 3Output: 7Explanation: Binary strings that satisfy the given c
15+ min read
Count of Binary strings of length N having atmost M consecutive 1s or 0s alternatively exactly K times
Given three integers, N, K and M. The task is to find out the number of binary strings of length N which always starts with 1, in which there can be at most M consecutive 1's or 0's and they alternate exactly K times.Examples: Input: N = 5, K = 3, M = 2 Output: 3 The 3 configurations are: 11001 1001
12 min read
Count of Binary strings having at most X consecutive 1s and Y consecutive 0s
Given two integers N and M (1 ≤ N, M ≤ 100) denoting the total number of 1s and 0s respectively. The task is to count the number of possible arrangements of these 0s and 1s such that any arrangement has at most X consecutive 1s and Y consecutive 0s (1 ≤ X, Y ≤ 10). As the number of arrangements can
7 min read
Generate a Binary String without any consecutive 0's and at most K consecutive 1's
Given two integers N and M, the task is to construct a binary string with the following conditions : The Binary String consists of N 0's and M 1'sThe Binary String has at most K consecutive 1's.The Binary String does not contain any adjacent 0's. If it is not possible to construct such a binary stri
7 min read
Count of binary strings of given length consisting of at least one 1
Given an integer N, the task is to print the number of binary strings of length N which at least one '1'. Examples: Input: 2 Output: 3 Explanation: "01", "10" and "11" are the possible strings Input: 3 Output: 7 Explanation: "001", "011", "010", "100", "101", "110" and "111" are the possible strings
3 min read
Count of groups of consecutive 1s in a given Binary String
Given a binary string S of size N, the task is to find the number of groups of 1s only in the string S. Examples: Input: S = "100110111", N = 9Output: 3Explanation: The following groups are of 1s only: Group over the range [0, 0] which is equal to "1".Group over the range [3, 4] which is equal to "1
5 min read
Count number of binary strings without consecutive 1’s : Set 2
Given a positive integer N, the task is to count all possible distinct binary strings of length N such that there are no consecutive 1’s. Examples: Input: N = 5 Output: 5 Explanation: The non-negative integers <= 5 with their corresponding binary representations are: 0 : 0 1 : 1 2 : 10 3 : 11 4 :
15+ min read
Number of Binary Strings of length N with K adjacent Set Bits
Given [Tex]n [/Tex]and [Tex]k [/Tex]. The task is to find the number of binary strings of length n out of 2n such that they satisfy f(bit string) = k. Where, f(x) = Number of times a set bit is adjacent to another set bit in a binary string x.For Example:f(011101101) = 3f(010100000) = 0f(111111111)
15+ min read
Count of binary strings of length N having equal count of 0's and 1's
Given an integer N, the task is to find the number of binary strings possible of length N having same frequency of 0s and 1s. If such string is possible of length N, print -1. Note: Since the count can be very large, return the answer modulo 109+7.Examples: Input: N = 2 Output: 2 Explanation: All po
6 min read