Count binary strings with k times appearing adjacent two set bits in C++

We are given with integers N and K. We have binary strings of length N, containing 0’s and 1’s only. The goal is to find the number of such strings of length N that have K consecutive 1’s. I.e, if N=3, and K=2, then count all 3-digit binary strings possible that have 2 consecutive 1’s.

Example − 111, here adjacent 1’s appear twice ( K times ).

In 011 and 110 adjacent 1’s appeared once only.

We will solve this by storing the results of previous values.

Taking 3D array count[x][y][z]. Where x is N, y is K and z is last digit of string ( 0 or 1 )

• For N=1, strings will be “0” and “1”. Count of adjacent 1’s=0.

So for any K. If N=1, count=0.

count[1][K][0] = count[1][K][1] = 0.

• When last digit is 0, To make adjacent 1’s count as K

All digits of length N-1 with K ones + last 0 → new length = N

If the count of K adjacent 1’s was C then adding 0 at the end won’t change that count.

count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]

• When last digit is 1, To make adjacent 1’s count as K

All digits of length N-1 ending with 0 with K ones + last 1 → new length = N,

count[N-1][K][0]

All digits of length N-1 ending with 1 with K-1 ones + last 1 → new length = N,

count[N-1][K-1][1]

count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]

Total such strings= count[N][K][0] + count[N][K][1]

Input

N=4, K=2

Output

Count of strings: 2

Explanation − 1110, 0111 are the only strings of length 4 where adjacent 1’s appear twice only.

1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times

Input

N=3, K=1

Output

Count of strings: 2

Explanation − 110, 011. are the only strings of length 3where adjacent 1’s appear once.

In 111 adjacent 1’s appear twice.

Approach used in the below program is as follows

• Integers N and K store the length of strings and no. of times adjacent 1’s appear in each.

• Function stringcount(int n, int k) takes n and k as parameters and returns the count of strings with K times adjacent 1’s.

• Array count[i][j][0/1] is used to store the count of strings of length i with j adjacent 1’s ending with 0 or 1.

• Initial condition is count[1][0][0] = 1; count[1][0][1] = 1;

• Now start from 2 length strings ( i=2) to n length. For each such string check count of K times adjacent 1’s. j=0;j<=k, from previous counts. Update current count[i][j][0] and count[i][j][1].

• If j-1>=0, the count of adjacent 1’s is greater than 1. Then update count of strings ending with 1 as count[i][j][1] + count[i - 1][j - 1][1];

• At the end add count[n][k][0] and count[n][k][1]. Store it as a result.

• Return the result as desired count.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int stringcount(int n, int k){    //count of strings with length=n and adajcent 1's=k    int count[n + 1][k + 1][2]={0};    //count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0    //count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1    // If n = 1 and k = 0.    count[1][0][0] = 1;    count[1][0][1] = 1;    for (int i = 2; i <= n; i++) {       // number of adjacent 1's can not exceed i-1       for (int j = 0; j <= k; j++) {          count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];          count[i][j][1] = count[i - 1][j][0];       if (j - 1 >= 0)          count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];       }    }    int result=count[n][k][0]+count[n][k][1];    return result; } int main(){    int N = 6, K = 3;    cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);    return 0; }

Output

Strings of length 6 and 3 adjacent 1's in each :7