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 <= k; 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. import java.util.*; import java.io.*; 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 |
PHP
<?php // PHP program to count number of binary strings // with k times appearing consecutive 1's. function 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 = array_fill (0, $n + 1, array_fill (0, $k + 1, array_fill (0, 2, 0))); // If n = 1 and k = 0. $dp [1][0][0] = 1; $dp [1][0][1] = 1; for ( $i = 2; $i <= $n ; $i ++) { // number of adjacent 1's can not exceed i-1 for ( $j = 0; $j < $i ; $j ++) { if (isset( $dp [ $i ][ $j ][0])||isset( $dp [ $i ][ $j ][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 >= 0 && isset( $dp [ $i ][ $j ][1])) $dp [ $i ][ $j ][1] += $dp [ $i - 1][ $j - 1][1]; } } return $dp [ $n ][ $k ][0] + $dp [ $n ][ $k ][1]; } // Driver code $n =5; $k =2; echo countStrings( $n , $k ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to count number // of binary strings with k times // appearing consecutive 1's. function 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. let dp = new Array(n + 1); for (let i = 0; i < n + 1; i++) { dp[i] = new Array(k + 1); for (let j = 0; j < k + 1; j++) { dp[i][j] = new Array(2); for (let l = 0 ; l < 2; l++) { dp[i][j][l] = 0; } } } // If n = 1 and k = 0. dp[1][0][0] = 1; dp[1][0][1] = 1; for (let i = 2; i <= n; i++) { // Number of adjacent 1's can not exceed i-1 for (let 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 let n = 5, k = 2; document.write(countStrings(n, k)); // This code is contributed by rag2127 </script> |
Output:
6
Time Complexity : O(n2)
Auxiliary Space: O(n2)
Contact Us