Given two integers N and K, the task is to count the number of ways to make a binary string of length N such that 0s always occur together in a group of size K.
Examples:
Input: N = 3, K = 2
Output : 3
No of binary strings:
111
100
001
Input : N = 4, K = 2
Output : 5
This problem can easily be solved using dynamic programming. Let dp[i] be the number of binary strings of length i satisfying the condition.
From the condition it can be deduced that:
- dp[i] = 1 for 1 <= i < k.
- Also dp[k] = 2 since a binary string of length K will either be a string of only zeros or only ones.
- Now if we consider for i > k. If we decide the ith character to be ‘1’, then dp[i] = dp[i-1] since the number of binary strings would not change. However if we decide the ith character to be ‘0’, then we require that previous k-1 characters should also be ‘0’ and hence dp[i] = dp[i-k]. Therefore dp[i] will be the sum of these 2 values.
Thus,
dp[i] = dp[i - 1] + dp[i - k]
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;const int mod = 1000000007;// Function to return no of ways to build a binary // string of length N such that 0s always occur // in groups of size Kint noOfBinaryStrings(int N, int k){ int dp[100002]; for (int i = 1; i <= k - 1; i++) { dp[i] = 1; } dp[k] = 2; for (int i = k + 1; i <= N; i++) { dp[i] = (dp[i - 1] + dp[i - k]) % mod; } return dp[N];}// Driver Codeint main(){ int N = 4; int K = 2; cout << noOfBinaryStrings(N, K); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int mod = 1000000007;// Function to return no of ways to build a binary // string of length N such that 0s always occur // in groups of size Kstatic int noOfBinaryStrings(int N, int k){ int dp[] = new int[100002]; for (int i = 1; i <= k - 1; i++) { dp[i] = 1; } dp[k] = 2; for (int i = k + 1; i <= N; i++) { dp[i] = (dp[i - 1] + dp[i - k]) % mod; } return dp[N];}// Driver Codepublic static void main(String[] args) { int N = 4; int K = 2; System.out.println(noOfBinaryStrings(N, K));}}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the# above approach mod = 1000000007; # Function to return no of ways to # build a binary string of length N# such that 0s always occur in # groups of size K def noOfBinaryStrings(N, k) : dp = [0] * 100002; for i in range(1, K) : dp[i] = 1; dp[k] = 2; for i in range(k + 1, N + 1) : dp[i] = (dp[i - 1] + dp[i - k]) % mod; return dp[N]; # Driver Code if __name__ == "__main__" : N = 4; K = 2; print(noOfBinaryStrings(N, K)); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG { static int mod = 1000000007;// Function to return no of ways to build // a binary string of length N such that // 0s always occur in groups of size Kstatic int noOfBinaryStrings(int N, int k){ int []dp = new int[100002]; for (int i = 1; i <= k - 1; i++) { dp[i] = 1; } dp[k] = 2; for (int i = k + 1; i <= N; i++) { dp[i] = (dp[i - 1] + dp[i - k]) % mod; } return dp[N];}// Driver Codepublic static void Main() { int N = 4; int K = 2; Console.WriteLine(noOfBinaryStrings(N, K));}}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript implementation of the approachlet mod = 1000000007;// Function to return no of ways to build a binary // string of length N such that 0s always occur // in groups of size Kfunction noOfBinaryStrings(N,k){ let dp = new Array(100002); for (let i = 1; i <= k - 1; i++) { dp[i] = 1; } dp[k] = 2; for (let i = k + 1; i <= N; i++) { dp[i] = (dp[i - 1] + dp[i - k]) % mod; } return dp[N];}// Driver Codelet N = 4;let K = 2;document.write(noOfBinaryStrings(N, K));// This code is contributed by rag2127.</script> |
PHP
<?php// PHP implementation of the above approach$mod = 1000000007;// Function to return no of ways to // build a binary string of length N // such that 0s always occur in groups// of size Kfunction noOfBinaryStrings($N, $k){ global $mod; $dp = array(0, 100002, NULL); for ($i = 1; $i <= $k - 1; $i++) { $dp[$i] = 1; } $dp[$k] = 2; for ($i = $k + 1; $i <= $N; $i++) { $dp[$i] = ($dp[$i - 1] + $dp[$i - $k]) % $mod; } return $dp[$N];}// Driver Code$N = 4;$K = 2;echo noOfBinaryStrings($N, $K);// This code is contributed by ita_c ?> |
Output
5
Another Approach: Recursion + memoization
In this approach we solve the problem with the help of recursive call and use a dp array to check that we previously computed the same subproblem.
Implementation Steps:
- Create a array of dp and initialize it with -1 to check that we previous computed the same subproblem.
- Initialize base cases.
- If computed then return dp[n].
- Create a variable ans to store the final result.
- Now recursively call the function first n-1 and second with n-k.
- At last return answer store in ans.
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// to handle large valuesconst int mod = 1000000007;// to store subproblemsint dp[100002];// Function to return no of ways to build a binary // string of length N such that 0s always occur // in groups of size Kint countBinaryStrings(int n, int k) { // Base Case if (n <= 0) { return 1; } // previous computed if (dp[n] != -1) { return dp[n]; } // recursive calls int ans = (countBinaryStrings(n-1, k) + ((n >= k) ? countBinaryStrings(n-k, k) : 0)) % mod; // update DP dp[n] = ans; // return final answer return ans;}// Driver codeint main() { int n = 4, k = 2; // fill dp with -1 memset(dp, -1, sizeof(dp)); // function call cout << countBinaryStrings(n, k) << endl; return 0;} |
Java
// Java program for above approachimport java.util.Arrays;public class GFG { // to handle large values static final int mod = 1000000007; // to store subproblems static int[] dp; // Function to return the number of ways to build a binary // string of length N such that 0s always occur // in groups of size K static int countBinaryStrings(int n, int k) { // Base Case if (n <= 0) { return 1; } // Previous computed if (dp[n] != -1) { return dp[n]; } // Recursive calls int ans = (countBinaryStrings(n - 1, k) + ((n >= k) ? countBinaryStrings(n - k, k) : 0)) % mod; // Update DP dp[n] = ans; // Return the final answer return ans; } // Driver code public static void main(String[] args) { int n = 4, k = 2; // Fill dp with -1 dp = new int[n + 1]; Arrays.fill(dp, -1); // Function call System.out.println(countBinaryStrings(n, k)); }} |
Python3
# to handle large valuesmod = 1000000007# to store subproblemsdp = [-1] * 100002# Function to return the number of ways to build a binary # string of length N such that 0s always occur in groups of size Kdef countBinaryStrings(n, k): # Base Case if n == 0: return 1 # Check if the subproblem is already computed if dp[n] != -1: return dp[n] # Recursive calls ans = (countBinaryStrings(n - 1, k) + (countBinaryStrings(n - k, k) if n >= k else 0)) % mod # Update DP dp[n] = ans # Return the final answer return ans# Driver coden = 4k = 2# Fill dp with -1dp = [-1] * (n + 1)# Function callprint(countBinaryStrings(n, k))# This code is contributed by rambabuguphka |
C#
using System;public class GFG { // to handle large values const int mod = 1000000007; // to store subproblems static int[] dp; // Function to return the number of ways to build a // binary string of length N such that 0s always occur // in groups of size K static int CountBinaryStrings(int n, int k) { // Base Case if (n <= 0) { return 1; } // previous computed if (dp[n] != -1) { return dp[n]; } // recursive calls int ans = (CountBinaryStrings(n - 1, k) + ((n >= k) ? CountBinaryStrings(n - k, k) : 0)) % mod; // update DP dp[n] = ans; // return the final answer return ans; } // Driver code static void Main() { int n = 4, k = 2; // initialize dp with -1 dp = new int[100002]; for (int i = 0; i < dp.Length; i++) { dp[i] = -1; } // function call Console.WriteLine(CountBinaryStrings(n, k)); }} |
Javascript
// to handle large valuesconst mod = 1000000007;// to store subproblemslet dp = new Array(100002);// Function to return no of ways to build a binary // string of length N such that 0s always occur // in groups of size Kfunction countBinaryStrings(n, k) { // Base Case if (n <= 0) { return 1; } // previous computed if (dp[n] != -1) { return dp[n]; } // recursive calls let ans = (countBinaryStrings(n - 1, k) + ((n >= k) ? countBinaryStrings(n - k, k) : 0)) % mod; // update DP dp[n] = ans; // return final answer return ans;}// Driver codelet n = 4, k = 2;// fill dp with -1dp.fill(-1);// function callconsole.log(countBinaryStrings(n, k)); |
Output:
5
Time complexity: O(N)
Auxiliary Space: O(N)
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!
