# 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 = 2Output: 6Explanation: 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: 8Approach: 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++#include using namespace std;int dp[1001];int cntString(int n, int k){ if (n == 0) { return 1; } if (dp[n] != -1) { return dp[n]; } int ans = 0; if (n >= k) { ans += cntString(n – k, k); } ans += cntString(n – 1, k); return dp[n] = ans;}int cntStringAll(int N, int K){ memset(dp, -1, sizeof(dp)); int cnt = 0; for (int i = 1; i { if (n == 0) { return 1; } if (dp[n] != -1) { return dp[n]; } let ans = 0; if (n >= k) { ans += cntString(n – k, k); } ans += cntString(n – 1, k); return dp[n] = ans; } const cntStringAll = (N, K) => { let cnt = 0; for (let i = 1; i