Count of Binary Strings of length at most N with set bit count as multiple of K
Given two integers N and K, the task is to find the count of binary strings of at most N length that can be formed such that the count of consecutive 1ās is always a multiple of K.
Example:
Input: N = 3, K = 2
Output: 6
Explanation: Binary strings of atmost N length containing consecutive 1ās as a multiple of K are as follows:
- Length 1: ā0ā, contains 0 consecutive 1.
- Length 2: ā00ā, ā11ā, contains 0 and 2 consecutive 1ās respectively.
- Length 3: ā000ā, ā011ā, ā110ā, contains 0 and two different combinations of 2 consecutive 1ās respectively.
So, total number of strings that can be formed is 6.
Input: N = 5, K = 4
Output: 8
Approach: The given problem can be solved with the help of Dynamic Programming using memoization. Follow the below steps to solve the given problem:
- Create a recursive function cntStrings(N, K), which returns the number of strings of N length having the consecutive 1ās as multiples of K. This can be done by assigning 1 to the next K consecutive indices from the current index and recursively calling for the remaining string or assigning 0 to the current index and recursively calling for the remaining string.
- Create an array dp[] which stores the memorized values of the above recursive function.
- Call the function cntStrings(i, K) for all possible values of i in the range [1, N] and store their sum in a variable cnt.
- The value stored in cnt is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int dp[1001]; // Recursive function to find the count // of valid binary strings of length n int cntString( int n, int k) { // Base Case if (n == 0) { return 1; } // If current value is already calculated if (dp[n] != -1) { return dp[n]; } // Stores the current answer int ans = 0; // Case for element at next k indices as 1 if (n >= k) { ans += cntString(n - k, k); } // Case for element at current index as 0 ans += cntString(n - 1, k); // Return ans with storing it in dp[] return dp[n] = ans; } // Function to find the count of valid // binary strings of atmost N length int cntStringAll( int N, int K) { // Initializing all elements with -1 memset (dp, -1, sizeof (dp)); // Stores the final answer int cnt = 0; // Iterate and calculate the total // possible binary strings of each // length in the range [1, N] for ( int i = 1; i <= N; i++) { cnt += cntString(i, K); } // Return Answer return cnt; } // Driver Code int main() { int N = 5; int K = 4; cout << cntStringAll(N, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { static int dp[] = new int [ 1001 ]; // Recursive function to find the count // of valid binary strings of length n static int cntString( int n, int k) { // Base Case if (n == 0 ) { return 1 ; } // If current value is already calculated if (dp[n] != - 1 ) { return dp[n]; } // Stores the current answer int ans = 0 ; // Case for element at next k indices as 1 if (n >= k) { ans += cntString(n - k, k); } // Case for element at current index as 0 ans += cntString(n - 1 , k); // Return ans with storing it in dp[] return dp[n] = ans; } // Function to find the count of valid // binary strings of atmost N length static int cntStringAll( int N, int K) { // Initializing all elements with -1 for ( int i = 0 ; i < 1001 ; i++) dp[i] = - 1 ; // Stores the final answer int cnt = 0 ; // Iterate and calculate the total // possible binary strings of each // length in the range [1, N] for ( int i = 1 ; i <= N; i++) { cnt += cntString(i, K); } // Return Answer return cnt; } // Driver Code public static void main(String[] args) { int N = 5 ; int K = 4 ; System.out.println(cntStringAll(N, K)); } } // This code is contributed by dwivediyash |
Python3
# python program for the above approach dp = [ - 1 for _ in range ( 1001 )] # Recursive function to find the count # of valid binary strings of length n def cntString(n, k): # Base Case if (n = = 0 ): return 1 # If current value is already calculated if (dp[n] ! = - 1 ): return dp[n] # Stores the current answer ans = 0 # Case for element at next k indices as 1 if (n > = k): ans + = cntString(n - k, k) # Case for element at current index as 0 ans + = cntString(n - 1 , k) # Return ans with storing it in dp[] dp[n] = ans return dp[n] # Function to find the count of valid # binary strings of atmost N length def cntStringAll(N, K): # Stores the final answer cnt = 0 # Iterate and calculate the total # possible binary strings of each # length in the range [1, N] for i in range ( 1 , N + 1 ): cnt + = cntString(i, K) # Return Answer return cnt # Driver Code if __name__ = = "__main__" : N = 5 K = 4 print (cntStringAll(N, K)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; public class GFG { static int []dp = new int [1001]; // Recursive function to find the count // of valid binary strings of length n static int cntString( int n, int k) { // Base Case if (n == 0) { return 1; } // If current value is already calculated if (dp[n] != -1) { return dp[n]; } // Stores the current answer int ans = 0; // Case for element at next k indices as 1 if (n >= k) { ans += cntString(n - k, k); } // Case for element at current index as 0 ans += cntString(n - 1, k); // Return ans with storing it in dp[] return dp[n] = ans; } // Function to find the count of valid // binary strings of atmost N length static int cntStringAll( int N, int K) { // Initializing all elements with -1 for ( int i = 0; i < 1001; i++) dp[i] = -1; // Stores the final answer int cnt = 0; // Iterate and calculate the total // possible binary strings of each // length in the range [1, N] for ( int i = 1; i <= N; i++) { cnt += cntString(i, K); } // Return Answer return cnt; } // Driver Code public static void Main(String[] args) { int N = 5; int K = 4; Console.WriteLine(cntStringAll(N, K)); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach let dp = new Array(1001).fill(-1); // Recursive function to find the count // of valid binary strings of length n const cntString = (n, k) => { // Base Case if (n == 0) { return 1; } // If current value is already calculated if (dp[n] != -1) { return dp[n]; } // Stores the current answer let ans = 0; // Case for element at next k indices as 1 if (n >= k) { ans += cntString(n - k, k); } // Case for element at current index as 0 ans += cntString(n - 1, k); // Return ans with storing it in dp[] return dp[n] = ans; } // Function to find the count of valid // binary strings of atmost N length const cntStringAll = (N, K) => { // Stores the final answer let cnt = 0; // Iterate and calculate the total // possible binary strings of each // length in the range [1, N] for (let i = 1; i <= N; i++) { cnt += cntString(i, K); } // Return Answer return cnt; } // Driver Code let N = 5; let K = 4; document.write(cntStringAll(N, K)); // This code is contributed by rakeshsahni </script> |
Output
8
Time Complexity: O(N)
Auxiliary Space: O(N)