Given an integer N, the task is to count the number of binary strings possible such that there is no substring of length ? 3 of all 1’s. This count can become very large so print the answer modulo 109 + 7.
Examples:
Input: N = 4
Output: 13
All possible valid strings are 0000, 0001, 0010, 0100,
1000, 0101, 0011, 1010, 1001, 0110, 1100, 1101 and 1011.
Input: N = 2
Output: 4
Approach: For every value from 1 to N, the only required strings are in which the number of substrings in which ‘1’ appears consecutively for just two times, one time or zero times. This can be calculated from 2 to N recursively. Dynamic programming can be used for memoization where dp[i][j] will store the number of possible strings such that 1 just appeared consecutively j times upto the ith index and j will be 0, 1, 2, …, i (may vary from 1 to N).
dp[i][0] = dp[i – 1][0] + dp[i – 1][1] + dp[i – 1][2] as in i position, 0 will be put.
dp[i][1] = dp[i – 1][0] as there is no 1 at the (i – 1)th position so we take that value.
dp[i][2] = dp[i – 1][1] as first 1 appeared at (i – 1)th position (consecutively) so we take that value directly.
The base cases are for length 1 string i.e. dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 0. So, find all the value dp[N][0] + dp[N][1] + dp[N][2] ans sum of all possible cases at the Nth position.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const long MOD = 1000000007;// Function to return the count of// all possible binary stringslong countStr(long N){ long dp[N + 1][3]; // Fill 0's in the dp array memset(dp, 0, sizeof(dp)); // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (int i = 2; i <= N; i++) { // dp[i][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans;}// Driver codeint main(){ long N = 8; cout << countStr(N); return 0;} |
Java
// Java implementation of the approach class GFG { final static long MOD = 1000000007; // Function to return the count of // all possible binary strings static long countStr(int N) { long dp[][] = new long[N + 1][3]; // Fill 0's in the dp array //memset(dp, 0, sizeof(dp)); // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (int i = 2; i <= N; i++) { // dp[i][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans; } // Driver code public static void main (String[] args) { int N = 8; System.out.println(countStr(N)); } }// This code is contributed by AnkitRai01 |
Python
# Python3 implementation of the approachMOD = 1000000007# Function to return the count of# all possible binary stringsdef countStr(N): dp = [[0 for i in range(3)] for i in range(N + 1)] # Base cases dp[1][0] = 1 dp[1][1] = 1 dp[1][2] = 0 for i in range(2, N + 1): # dp[i][j] is the number of possible # strings such that '1' just appeared # consecutively j times upto ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD # Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD dp[i][2] = dp[i - 1][1] % MOD # Taking all the possible cases that # can appear at the Nth position ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD return ans# Driver codeif __name__ == '__main__': N = 8 print(countStr(N))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System;class GFG { static long MOD = 1000000007; // Function to return the count of // all possible binary strings static long countStr(int N) { long [,]dp = new long[N + 1, 3]; // Base cases dp[1, 0] = 1; dp[1, 1] = 1; dp[1, 2] = 0; for (int i = 2; i <= N; i++) { // dp[i,j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1] + dp[i - 1, 2]) % MOD; // Taking previously calculated value dp[i, 1] = dp[i - 1, 0] % MOD; dp[i, 2] = dp[i - 1, 1] % MOD; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp[N, 0] + dp[N, 1] + dp[N, 2]) % MOD; return ans; } // Driver code public static void Main () { int N = 8; Console.WriteLine(countStr(N)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the approachvar MOD = 1000000007;// Function to return the count of// all possible binary stringsfunction countStr(N){ var dp = Array.from(Array(N+1), ()=> Array(3).fill(0)); // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (var i = 2; i <= N; i++) { // dp[i][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all the possible cases that // can appear at the Nth position var ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans;}// Driver codevar N = 8;document.write( countStr(N));// This code is contributed by itsok.</script> |
Output
149
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: Space Optimization
In previous approach the current computation is depend upon the previous 3 computation dp[i][0] = (dp[i – 1][0] + dp[i – 1][1] + dp[i – 1][2]) So to optimize space we just required previous 3 computation to get the current answer.
Implementation steps:
- Initialize three variables dp0, dp1, and dp2 to 1, 1, and 0, respectively, which represent the number of binary strings that end in 0, end in 1 with the previous digit being 0, and end in 1 with the previous digit being 1.
- Run a loop from i = 2 to i = N, and in each iteration:
- a. Calculate the new value of dp0 as the sum of dp0, dp1, and dp2, modulo MOD.
- b. Update the value of dp2 as the previous value of dp1.
- c. Update the value of dp1 as the previous value of dp0.
- Calculate the answer by adding the values of dp0, dp1, and dp2, modulo MOD, and return it as the output of the function.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;const long MOD = 1000000007;// Function to return the count of// all possible binary stringslong countStr(long N){ long dp0 = 1; long dp1 = 1; long dp2 = 0; for (int i = 2; i <= N; i++) { // dp[i%3][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index long temp = dp0; dp0 = (dp0 + dp1 + dp2) % MOD; // Taking previously calculated value dp2 = dp1; dp1 = temp; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp0 + dp1 + dp2) % MOD; return ans;}// Driver codeint main(){ long N = 8; cout << countStr(N); return 0;} |
Java
import java.io.*;import java.lang.*;import java.util.*;class Main { public static void main(String[] args) throws java.lang.Exception { long N = 8; System.out.println(countStr(N)); } // Function to return the count of // all possible binary strings public static long countStr(long N) { long dp0 = 1; long dp1 = 1; long dp2 = 0; for (int i = 2; i <= N; i++) { // dp[i%3][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index long temp = dp0; dp0 = (dp0 + dp1 + dp2) % 1000000007; // Taking previously calculated value dp2 = dp1; dp1 = temp; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp0 + dp1 + dp2) % 1000000007; return ans; }} |
Python3
MOD = 1000000007# Function to return the count of all possible binary stringsdef countStr(N): dp0 = 1 dp1 = 1 dp2 = 0 for i in range(2, N + 1): # dp[i%3][j] is the number of possible strings such that '1' just appeared consecutively j times upto ith index temp = dp0 dp0 = (dp0 + dp1 + dp2) % MOD # Taking previously calculated value dp2 = dp1 dp1 = temp # Taking all the possible cases that can appear at the Nth position ans = (dp0 + dp1 + dp2) % MOD return ans# Driver codeN = 8print(countStr(N)) |
C#
using System;class GFG { // Function to return the count of // all possible binary strings public static long CountStr(long N) { long dp0 = 1; long dp1 = 1; long dp2 = 0; for (int i = 2; i <= N; i++) { // dp[i%3][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index long temp = dp0; dp0 = (dp0 + dp1 + dp2) % 1000000007; // Taking previously calculated value dp2 = dp1; dp1 = temp; } // Taking all the possible cases that // can appear at the Nth position long ans = (dp0 + dp1 + dp2) % 1000000007; return ans; } // Driver code public static void Main(string[] args) { long N = 8; Console.WriteLine(CountStr(N)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
const MOD = 1000000007;// Function to return the count of// all possible binary stringsfunction countStr(N) { let dp0 = 1; let dp1 = 1; let dp2 = 0; for (let i = 2; i <= N; i++) { // dp[i%3][j] is the number of possible // strings such that '1' just appeared // consecutively j times upto ith index let temp = dp0; dp0 = (dp0 + dp1 + dp2) % MOD; // Taking previously calculated value dp2 = dp1; dp1 = temp; } // Taking all the possible cases that // can appear at the Nth position let ans = (dp0 + dp1 + dp2) % MOD; return ans;}// Driver codelet N = 8;console.log(countStr(N)); |
Output
149
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
