Given a positive integer N, the task is to find the number of binary strings of length N which contains “11” as a substring.
Examples:
Input: N = 2
Output: 1
Explanation: The only string of length 2 that has “11” as a substring is “11”.Input: N = 12
Output: 3719
Approach: The idea is to derive the number of possibilities of having “11” as a substring for binary representations starting with 0 or 1 based on the following observations:
- If the first bit is 0, then the starting bit does not contribute to the string having “11” as a substring. Therefore, the remaining (N – 1) bits have to form a string having “11” as a substring.
- If the first bit is 1 and the following bit is also 1, then there exists 2(N – 2) strings having “11” as a substring.
- If the first bit is 1 but the following bit is 0, then a string having “11” as a substring can be formed with remaining (N – 2) bits.
- Therefore, the recurrence relation to generate all the binary strings of length N is:
dp[i] = dp[i – 1] + dp[i – 2] + 2(i – 2)
where,
dp[i] is the string of length i having “11” as a substring.
and dp[0] = dp[1] = 0.
Recursive Solution (Naive Solution):
here we have to find the number of possibilities having “11” as a substring for binary representation starting with 0 or 1 based on the observations. so above mentioned approach is for that. but in a recursive solution if we want to find the solution for i then that should be calculated as follows,
binaryStrings(i) = binaryStrings(i-1) + binaryStrings(i-2) + 2(i-2)
which can be solved recursively as follow.
C++
// Recursive C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count binary strings of length N having substring "11"int binaryStrings(int N) { // Base Cases if (N == 0 || N == 1) { return 0; } // Recursively calculate answer for current state return binaryStrings(N - 1) + binaryStrings(N - 2) + (1 << (N - 2)); // 1<<(i-2) means power of 2^(i-2)}// Driver Codeint main(){ int N = 12; cout << binaryStrings(N); return 0;} |
Java
import java.util.*;public class Main { // Function to count binary strings of length N having // substring "11" static int BinaryStrings(int N) { // Base Cases if (N == 0 || N == 1) { return 0; } // Recursively calculate answer for current state return BinaryStrings(N - 1) + BinaryStrings(N - 2) + (1 << (N - 2)); // 1<<(i-2) means power of 2^(i-2) } // Driver Code public static void main(String[] args) { int N = 12; System.out.println(BinaryStrings(N)); }} |
Python3
# Function to count binary strings of length N having substring "11"def binaryStrings(N: int) -> int: # Base Cases if N == 0 or N == 1: return 0 # Recursively calculate answer for current state return binaryStrings(N - 1) + binaryStrings(N - 2) + (1 << (N - 2)) # 1<<(i-2) means power of 2^(i-2)# Driver Codeif __name__ == "__main__": N = 12 print(binaryStrings(N)) |
C#
using System;public class Program { // Function to count binary strings of length N having substring "11" static int BinaryStrings(int N) { // Base Cases if (N == 0 || N == 1) { return 0; } // Recursively calculate answer for current state return BinaryStrings(N - 1) + BinaryStrings(N - 2) + (1 << (N - 2)); // 1<<(i-2) means power of 2^(i-2) } // Driver Code public static void Main() { int N = 12; Console.WriteLine(BinaryStrings(N)); }} |
Javascript
// Function to count binary strings of length N having substring "11"function binaryStrings(N) { // Base Cases if (N == 0 || N == 1) { return 0; } // Recursively calculate answer for current state return binaryStrings(N - 1) + binaryStrings(N - 2) + (1 << (N - 2)); // 1<<(i-2) means power of 2^(i-2)}// Driver Codelet N = 12;console.log(binaryStrings(N)); |
Output
3719
Optimized Solution:
Follow the steps below to solve the problem:
- Initialize an array, say dp[], of size (N + 1) and assign dp[0] as 0 and dp[1] as 0.
- Precompute the first N powers of 2 and store it in an array, say power[].
- Iterate over the range [2, N] and update dp[i] as (dp[i – 1] + dp[i – 2] + power[i – 2]).
- After completing the above steps, print the value of dp[N] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count binary strings// of length N having substring "11"void binaryStrings(int N){ // Initialize dp[] of size N + 1 int dp[N + 1]; // Base Cases dp[0] = 0; dp[1] = 0; // Iterate over the range [2, N] for (int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2] + (1<<(i-2)); // 1<<(i-2) means power of 2^(i-2) } // Print total count of substrings cout << dp[N];}// Driver Codeint main(){ int N = 12; binaryStrings(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count binary strings// of length N having substring "11"static void binaryStrings(int N){ // Initialize dp[] of size N + 1 int[] dp = new int[N + 1]; // Base Cases dp[0] = 0; dp[1] = 0; // Stores the first N powers of 2 int[] power = new int[N + 1]; power[0] = 1; // Generate for(int i = 1; i <= N; i++) { power[i] = 2 * power[i - 1]; } // Iterate over the range [2, N] for(int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2] + power[i - 2]; } // Print total count of substrings System.out.println(dp[N]);}// Driver Codepublic static void main(String[] args){ int N = 12; binaryStrings(N);}}// This code is contributed by ukasp |
Python3
# Python3 program for the above approach# Function to count binary strings# of length N having substring "11"def binaryStrings(N): # Initialize dp[] of size N + 1 dp = [0]*(N + 1) # Base Cases dp[0] = 0 dp[1] = 0 # Stores the first N powers of 2 power = [0]*(N + 1) power[0] = 1 # Generate for i in range(1, N + 1): power[i] = 2 * power[i - 1] # Iterate over the range [2, N] for i in range(2, N + 1): dp[i] = dp[i - 1] + dp[i - 2] + power[i - 2] # Prtotal count of substrings print (dp[N])# Driver Codeif __name__ == '__main__': N = 12 binaryStrings(N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to count binary strings // of length N having substring "11" static void binaryStrings(int N) { // Initialize dp[] of size N + 1 int []dp = new int[N + 1]; // Base Cases dp[0] = 0; dp[1] = 0; // Stores the first N powers of 2 int []power = new int[N + 1]; power[0] = 1; // Generate for (int i = 1; i <= N; i++) { power[i] = 2 * power[i - 1]; } // Iterate over the range [2, N] for (int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2] + power[i - 2]; } // Print total count of substrings Console.WriteLine(dp[N]); } // Driver Code public static void Main() { int N = 12; binaryStrings(N); }}// This code is contributed by bgangwar59. |
Javascript
<script>// JavaScript program for the above approach // Function to count binary strings // of length N having substring "11" function binaryStrings(N) { // Initialize dp of size N + 1 var dp = Array(N + 1).fill(0); // Base Cases dp[0] = 0; dp[1] = 0; // Stores the first N powers of 2 var power = Array(N+1).fill(0); power[0] = 1; // Generate for (i = 1; i <= N; i++) { power[i] = 2 * power[i - 1]; } // Iterate over the range [2, N] for (i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2] + power[i - 2]; } // Print total count of substrings document.write(dp[N]); } // Driver Code var N = 12; binaryStrings(N);// This code contributed by aashish1995</script> |
Output
3719
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!
