Tutorialspoint.dev

Count binary strings with k times appearing adjacent two set bits

Given two integers n and k, count the number of binary strings of length n with k as number of times adjacent 1’s appear.

Examples:

Input  : n = 5, k = 2
Output : 6
Explanation:
Binary strings of length 5 in which k number of times
two adjacent set bits appear.
00111  
01110
11100
11011
10111
11101

Input  : n = 4, k = 1
Output : 3
Explanation:
Binary strings of length 3 in which k number of times
two adjacent set bits appear.
0011  
1100
0110


Lets try writing the recursive function for the above problem statement:
1) n = 1, only two binary strings exist with length 1, not having any adjacent 1’s
      String 1 : “0”
      String 2 : “1”

2) For all n > 1 and all k, two cases arise
      a) Strings ending with 0 : String of length n can be created by appending 0 to all strings of length n-1 having k times two adjacent 1’s ending with both 0 and 1 (Having 0 at n’th position will not change the count of adjacent 1’s).
      b) Strings ending with 1 : String of length n can be created by appending 1 to all strings of length n-1 having k times adjacent 1’s and ending with 0 and to all strings of length n-1 having k-1 adjacent 1’s and ending with 1.

Example: let s = 011 i.e. a string ending with 1 having adjacent count as 1. Adding 1 to it, s = 0111 increase the count of adjacent 1.



Let there be an array dp[i][j][2] where dp[i][j][0]
denotes number of binary strings with length i having
j number of two adjacent 1's and ending with 0.
Similarly dp[i][j][1] denotes the same binary strings
with length i and j adjacent 1's but ending with 1.
Then: 
    dp[1][0][0] = 1 and dp[1][0][1] = 1
    For all other i and j,
        dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]
        dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1]

Then, output dp[n][k][0] + dp[n][k][1]

C++

// C++ program to count number of binary strings
// with k times appearing consecutive 1's.
#include<bits/stdc++.h>
using namespace std;
  
int countStrings(int n, int k)
{
    // dp[i][j][0] stores count of binary
    // strings of length i with j consecutive
    // 1's and ending at 0.
    // dp[i][j][1] stores count of binary
    // strings of length i with j consecutive
    // 1's and ending at 1.
    int dp[n+1][k+1][2];
    memset(dp, 0, sizeof(dp));
  
    // If n = 1 and k = 0. 
    dp[1][0][0] = 1;
    dp[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<i; j++)
        {
            dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
            dp[i][j][1] = dp[i-1][j][0];
  
            if (j-1 >= 0)
                dp[i][j][1] += dp[i-1][j-1][1];
        }
    }
  
    return dp[n][k][0] + dp[n][k][1];
}
  
// Driver code
int main()
{
    int n=5, k=2;
    cout << countStrings(n, k);
    return 0;
}

Java

// Java program to count number of binary strings
// with k times appearing consecutive 1's.
class GFG 
{
  
    static int countStrings(int n, int k) 
    {
        // dp[i][j][0] stores count of binary
        // strings of length i with j consecutive
        // 1's and ending at 0.
        // dp[i][j][1] stores count of binary
        // strings of length i with j consecutive
        // 1's and ending at 1.
        int dp[][][] = new int[n + 1][k + 1][2];
  
        // If n = 1 and k = 0. 
        dp[1][0][0] = 1;
        dp[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 < i && j < k + 1; j++) 
            {
                dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
                dp[i][j][1] = dp[i - 1][j][0];
  
                if (j - 1 >= 0
                {
                    dp[i][j][1] += dp[i - 1][j - 1][1];
                }
            }
        }
  
        return dp[n][k][0] + dp[n][k][1];
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        int n = 5, k = 2;
        System.out.println(countStrings(n, k));
    }
}
  
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to count number of 
# binary strings with k times appearing 
# consecutive 1's.
def countStrings(n, k):
  
    # dp[i][j][0] stores count of binary
    # strings of length i with j consecutive
    # 1's and ending at 0.
    # dp[i][j][1] stores count of binary
    # strings of length i with j consecutive
    # 1's and ending at 1.
    dp = [[[0, 0] for __ in range(k + 1)] 
                  for _ in range(n + 1)]
  
    # If n = 1 and k = 0.
    dp[1][0][0] = 1
    dp[1][0][1] = 1
  
    for i in range(2, n + 1):
          
        # number of adjacent 1's can not exceed i-1
        for j in range(k + 1):
            dp[i][j][0] = (dp[i - 1][j][0] + 
                           dp[i - 1][j][1])
            dp[i][j][1] = dp[i - 1][j][0]
            if j >= 1:
                dp[i][j][1] += dp[i - 1][j - 1][1]
  
    return dp[n][k][0] + dp[n][k][1]
  
# Driver Code
if __name__ == '__main__':
    n = 5
    k = 2
    print(countStrings(n, k))
  
# This code is contributed by vibhu4agarwal

C#

// C# program to count number of binary strings
// with k times appearing consecutive 1's.
using System;
  
class GFG 
{
  
    static int countStrings(int n, int k) 
    {
        // dp[i][j][0] stores count of binary
        // strings of length i with j consecutive
        // 1's and ending at 0.
        // dp[i][j][1] stores count of binary
        // strings of length i with j consecutive
        // 1's and ending at 1.
        int [,,]dp = new int[n + 1, k + 1, 2];
  
        // If n = 1 and k = 0. 
        dp[1, 0, 0] = 1;
        dp[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 < i && j < k + 1; j++) 
            {
                dp[i, j, 0] = dp[i - 1, j, 0] + dp[i - 1, j, 1];
                dp[i, j, 1] = dp[i - 1, j, 0];
  
                if (j - 1 >= 0) 
                {
                    dp[i, j, 1] += dp[i - 1, j - 1, 1];
                }
            }
        }
  
        return dp[n, k, 0] + dp[n, k, 1];
    }
  
    // Driver code
    public static void Main(String[] args) 
    {
        int n = 5, k = 2;
        Console.WriteLine(countStrings(n, k));
    }
}
  
// This code contributed by Rajput-Ji

Output:

6

Time Complexity : O(n2)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter