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 codeint 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 Codeif __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 codelet 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)
This article is contributed by Aarti_Rathi and Ekta Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
