- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

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]**

N=4, K=2

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

N=3, K=1

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.

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.

#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; }

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

- Related Questions & Answers
- Check if a number has two adjacent set bits in C++
- Count set bits in an integer in C++
- Count set bits in a range in C++
- Count substrings with each character occurring at most k times in C++
- Binary Number with Alternating Bits in C++
- Minimum flips required to maximize a number with k set bits in C++.
- C/C++ Program to Count set bits in an integer?
- Prime Number of Set Bits in Binary Representation in C++
- Program to add two binary strings in C++
- Python Count set bits in a range?
- XOR of all elements of array with set bits equal to K in C++
- Count of strings where adjacent characters are of difference one in C++
- Count common subsequence in two strings in C++
- Count common characters in two strings in C++
- Maximum score after flipping a Binary Matrix atmost K times in C++

Advertisements