Number of ways to make binary string of length N such that 0s always occur together in groups of size K

0 0 7 minutes read

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 i^th character to be ‘1’, then dp[i] = dp[i-1] since the number of binary strings would not change. However if we decide the i^th 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 K
int 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 Code
int main()
{
    int N = 4;
    int K = 2;
    cout << noOfBinaryStrings(N, K);
 
    return 0;
}

Java

// Java implementation of the approach
import 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 K
static 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 Code
public 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 approach
using 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 K
static 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 Code
public 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 approach
 
let 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
function 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 Code
let 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 K
function 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

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 values
const int mod = 1000000007;
 
// to store subproblems
int 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 K
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 final answer
    return ans;
}
 
// Driver code
int 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 approach
 
import 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 values
mod = 1000000007
 
# to store subproblems
dp = [-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 K
 
 
def 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 code
n = 4
k = 2
 
# Fill dp with -1
dp = [-1] * (n + 1)
 
# Function call
print(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 values
const mod = 1000000007;
 
// to store subproblems
let 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 K
function 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 code
let n = 4,
    k = 2;
 
// fill dp with -1
dp.fill(-1);
 
// function call
console.log(countBinaryStrings(n, k));

Output:

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 zambiatek!