Given a positive integer N, the task is to count all possible distinct binary strings of length N such that there are no consecutive 1’s.
Examples:
Input: N = 5
Output: 5
Explanation:
The non-negative integers <= 5 with their corresponding binary representations are:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only 3 has two consecutive 1’s. Therefore required count = 5Input: N = 12
Output: 8
Dynamic Programming Approach: A dynamic programming approach has already been discussed in this article.
Approach: In this article, an approach using the concept of digit-dp is discussed.
- Similar to the digit-dp problem, a 3-dimensional table is created here to store the computed values. It is assumed that the N < 231 – 1, and the range of every number is only 2 (Either 0 or 1). Therefore, the dimensions of the table are taken as 32 x 2 x 2.
- After constructing the table, the given number is converted to a binary string.
- Then, the number is iterated. For every iteration:
- Check if the previous digit is a 0 or 1.
- If it is a 0, then the present number can either be a 0 or 1.
- But if the previous number is 1, then the present number has to be 0 because we can’t have two consecutive 1’s in the binary representation.
- Now, the table is exactly filled like the digit-dp problem.
Below is the implementation of the above approach
C++
// C++ program to count number of// binary strings without consecutive 1’s#include <bits/stdc++.h>using namespace std;// Table to store the solution of// every sub problemint memo[32][2][2];// Function to fill the table/* Here, pos: keeps track of current position. f1: is the flag to check if current number is less than N or not. pr: represents the previous digit*/int dp(int pos, int fl, int pr, string& bin){ // Base case if (pos == bin.length()) return 1; // Check if this subproblem // has already been solved if (memo[pos][fl][pr] != -1) return memo[pos][fl][pr]; int val = 0; // Placing 0 at the current position // as it does not violate the condition if (bin[pos] == '0') val = val + dp(pos + 1, fl, 0, bin); // Here flag will be 1 for the // next recursive call else if (bin[pos] == '1') val = val + dp(pos + 1, 1, 0, bin); // Placing 1 at this position only if // the previously inserted number is 0 if (pr == 0) { // If the number is smaller than N if (fl == 1) { val += dp(pos + 1, fl, 1, bin); } // If the digit at current position is 1 else if (bin[pos] == '1') { val += dp(pos + 1, fl, 1, bin); } } // Storing the solution to this subproblem return memo[pos][fl][pr] = val;}// Function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationint findIntegers(int num){ // Convert N to binary form string bin; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2) bin += "1"; else bin += "0"; num /= 2; } reverse(bin.begin(), bin.end()); // Initialising the table with -1. memset(memo, -1, sizeof(memo)); // Calling the function return dp(0, 0, 0, bin);}// Driver codeint main(){ int N = 12; cout << findIntegers(N); return 0;} |
Java
// Java program to count number of// binary Strings without consecutive 1’simport java.io.*;class GFG{ // Table to store the solution of// every sub problemstatic int [][][]memo = new int[32][2][2]; // Function to fill the table/* Here, pos: keeps track of current position. f1: is the flag to check if current number is less than N or not. pr: represents the previous digit*/static int dp(int pos, int fl, int pr, String bin){ // Base case if (pos == bin.length()) return 1; // Check if this subproblem // has already been solved if (memo[pos][fl][pr] != -1) return memo[pos][fl][pr]; int val = 0; // Placing 0 at the current position // as it does not violate the condition if (bin.charAt(pos) == '0') val = val + dp(pos + 1, fl, 0, bin); // Here flag will be 1 for the // next recursive call else if (bin.charAt(pos) == '1') val = val + dp(pos + 1, 1, 0, bin); // Placing 1 at this position only if // the previously inserted number is 0 if (pr == 0) { // If the number is smaller than N if (fl == 1) { val += dp(pos + 1, fl, 1, bin); } // If the digit at current position is 1 else if (bin.charAt(pos) == '1') { val += dp(pos + 1, fl, 1, bin); } } // Storing the solution to this subproblem return memo[pos][fl][pr] = val;} // Function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationstatic int findIntegers(int num){ // Convert N to binary form String bin = ""; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2 == 1) bin += "1"; else bin += "0"; num /= 2; } bin = reverse(bin); // Initialising the table with -1. for(int i = 0; i < 32; i++){ for(int j = 0; j < 2; j++){ for(int l = 0; l < 2; l++) memo[i][j][l] = -1; } } // Calling the function return dp(0, 0, 0, bin);}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver codepublic static void main(String[] args){ int N = 12; System.out.print(findIntegers(N)); }}// This code is contributed by sapnasingh4991 |
Python3
# Python program to count number of# binary strings without consecutive 1’s# Table to store the solution of# every sub problemmemo=[[[-1 for i in range(2)] for j in range(2)] for k in range(32)]# Function to fill the table''' Here,pos: keeps track of current position.f1: is the flag to check if current number is less than N or not.pr: represents the previous digit'''def dp(pos,fl,pr,bin): # Base case if (pos == len(bin)): return 1; # Check if this subproblem # has already been solved if (memo[pos][fl][pr] != -1): return memo[pos][fl][pr]; val = 0 # Placing 0 at the current position # as it does not violate the condition if (bin[pos] == '0'): val = val + dp(pos + 1, fl, 0, bin) # Here flag will be 1 for the # next recursive call elif (bin[pos] == '1'): val = val + dp(pos + 1, 1, 0, bin) # Placing 1 at this position only if # the previously inserted number is 0 if (pr == 0): # If the number is smaller than N if (fl == 1): val += dp(pos + 1, fl, 1, bin) # If the digit at current position is 1 elif (bin[pos] == '1'): val += dp(pos + 1, fl, 1, bin) # Storing the solution to this subproblem memo[pos][fl][pr] = val return val# Function to find the number of integers# less than or equal to N with no# consecutive 1’s in binary representationdef findIntegers(num): # Convert N to binary form bin="" # Loop to convert N # from Decimal to binary while (num > 0): if (num % 2): bin += "1" else: bin += "0" num //= 2 bin=bin[::-1]; # Calling the function return dp(0, 0, 0, bin)# Driver codeif __name__ == "__main__": N = 12 print(findIntegers(N)) |
C#
// C# program to count number of// binary Strings without consecutive 1’susing System;public class GFG{ // Table to store the solution of// every sub problemstatic int [,,]memo = new int[32,2,2]; // Function to fill the table/* Here, pos: keeps track of current position. f1: is the flag to check if current number is less than N or not. pr: represents the previous digit*/static int dp(int pos, int fl, int pr, String bin){ // Base case if (pos == bin.Length) return 1; // Check if this subproblem // has already been solved if (memo[pos,fl,pr] != -1) return memo[pos,fl,pr]; int val = 0; // Placing 0 at the current position // as it does not violate the condition if (bin[pos] == '0') val = val + dp(pos + 1, fl, 0, bin); // Here flag will be 1 for the // next recursive call else if (bin[pos] == '1') val = val + dp(pos + 1, 1, 0, bin); // Placing 1 at this position only if // the previously inserted number is 0 if (pr == 0) { // If the number is smaller than N if (fl == 1) { val += dp(pos + 1, fl, 1, bin); } // If the digit at current position is 1 else if (bin[pos] == '1') { val += dp(pos + 1, fl, 1, bin); } } // Storing the solution to this subproblem return memo[pos,fl,pr] = val;} // Function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationstatic int findints(int num){ // Convert N to binary form String bin = ""; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2 == 1) bin += "1"; else bin += "0"; num /= 2; } bin = reverse(bin); // Initialising the table with -1. for(int i = 0; i < 32; i++){ for(int j = 0; j < 2; j++){ for(int l = 0; l < 2; l++) memo[i,j,l] = -1; } } // Calling the function return dp(0, 0, 0, bin);}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver codepublic static void Main(String[] args){ int N = 12; Console.Write(findints(N)); }} // This code contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to count number of// binary strings without consecutive 1’s// Table to store the solution of// every sub problemvar memo = Array.from(Array(32), ()=>Array(2));for(var i =0;i<32;i++){ for(var j =0; j<2; j++) { memo[i][j] = new Array(2).fill(-1); }}// Function to fill the table/* Here, pos: keeps track of current position. f1: is the flag to check if current number is less than N or not. pr: represents the previous digit*/function dp(pos, fl, pr, bin){ // Base case if (pos == bin.length) return 1; // Check if this subproblem // has already been solved if (memo[pos][fl][pr] != -1) return memo[pos][fl][pr]; var val = 0; // Placing 0 at the current position // as it does not violate the condition if (bin[pos] == '0') val = val + dp(pos + 1, fl, 0, bin); // Here flag will be 1 for the // next recursive call else if (bin[pos] == '1') val = val + dp(pos + 1, 1, 0, bin); // Placing 1 at this position only if // the previously inserted number is 0 if (pr == 0) { // If the number is smaller than N if (fl == 1) { val += dp(pos + 1, fl, 1, bin); } // If the digit at current position is 1 else if (bin[pos] == '1') { val += dp(pos + 1, fl, 1, bin); } } // Storing the solution to this subproblem return memo[pos][fl][pr] = val;}// Function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationfunction findIntegers(num){ // Convert N to binary form var bin = ""; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2) bin += "1"; else bin += "0"; num =parseInt(num/2); } bin = bin.split('').reverse().join('') // Calling the function return dp(0, 0, 0, bin);}// Driver codevar N = 12;document.write( findIntegers(N));</script> |
Output
8
Time Complexity: O(L * log(N))
- O(log(N)) to convert the number from Decimal to binary.
- O(L) to fill the table, where L is the length of the binary form.
Auxiliary Space: O(32 * 2 * 2)
Efficient approach : DP tabulation (iterative)
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls. In this approach we use 3D DP store computation of subproblems and find the final result using iteration and not with the help of recursion.
Implementation Steps:
- Convert the given number N to its binary representation.
- Initialize a DP table of size n+1 x 2 x 2, where n is the number of digits in the binary representation of N.
- Loop through each digit of the binary representation of N and fill the DP table using the recurrence relation: dp[i][j | (l < limit)][l] += dp[i-1][j][k], where dp[i][j][k] represents the number of binary strings of length i that do not have consecutive 1s, and j and k represent whether the previous digit and current digit are both 1s, respectively.
- Sum up the number of valid binary strings of length N by adding dp[n][i][0] and dp[n][i][1] for i = 0 to 1.
- Return the final count of valid binary strings.
Implementation:
C++
// C++ program to count number of// binary strings without consecutive 1’s#include <bits/stdc++.h>using namespace std;// Function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationint findIntegers(int num){ // Convert N to binary form string bin; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2) bin += "1"; else bin += "0"; num /= 2; } reverse(bin.begin(), bin.end()); int n = bin.length(); // DP table to store the solutions int dp[n + 1][2][2]; memset(dp, 0, sizeof(dp)); // Initializing the DP table dp[0][0][0] = 1; // Loop through each digit for (int i = 1; i <= n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { int limit = (j ? 1 : bin[i - 1] - '0'); for (int l = 0; l <= limit; l++) { if (l == 1 && k == 1) continue; dp[i][j | (l < limit)][l] += dp[i - 1][j][k]; } } } } // Calculating the result int result = 0; for (int i = 0; i < 2; i++) { result += dp[n][i][0]; result += dp[n][i][1]; } // return the final answer return result;}// Driver codeint main(){ int N = 12; cout << findIntegers(N); return 0;} |
Java
// Java code for above approachimport java.util.Arrays;public class Main { // Function to find the number of integers // less than or equal to N with no // consecutive 1’s in binary representation static int findIntegers(int num) { // Convert N to binary form StringBuilder bin = new StringBuilder(); // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2 == 1) bin.append("1"); else bin.append("0"); num /= 2; } bin.reverse(); int n = bin.length(); // DP table to store the solutions int[][][] dp = new int[n + 1][2][2]; for (int[][] arr : dp) { for (int[] subArr : arr) { Arrays.fill(subArr, 0); } } // Initializing the DP table dp[0][0][0] = 1; // Loop through each digit for (int i = 1; i <= n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { int limit = (j == 1) ? 1 : (bin.charAt(i - 1) - '0'); for (int l = 0; l <= limit; l++) { if (l == 1 && k == 1) continue; dp[i][j | ((l < limit) ? 1 : 0)][l] += dp[i - 1][j][k]; } } } } // Calculating the result int result = 0; for (int i = 0; i < 2; i++) { result += dp[n][i][0]; result += dp[n][i][1]; } return result; } // Driver code public static void main(String[] args) { int N = 12; System.out.println(findIntegers(N)); }} |
Python3
# code# Python3 program to count number of# binary strings without consecutive 1’s# Function to find the number of integers# less than or equal to N with no# consecutive 1’s in binary representationdef findIntegers(num): # Convert N to binary form bin = "" # Loop to convert N # from Decimal to binary while num > 0: if num % 2 == 1: bin += "1" else: bin += "0" num //= 2 bin = bin[::-1] n = len(bin) # DP table to store the solutions dp = [[[0 for i in range(2)] for j in range(2)] for k in range(n + 1)] # Initializing the DP table dp[0][0][0] = 1 # Loop through each digit for i in range(1, n + 1): for j in range(2): for k in range(2): limit = 1 if j else int(bin[i - 1]) for l in range(limit + 1): if l == 1 and k == 1: continue dp[i][j | (l < limit)][l] += dp[i - 1][j][k] # Calculating the result result = 0 for i in range(2): result += dp[n][i][0] result += dp[n][i][1] # return the final answer return result# Driver codeN = 12print(findIntegers(N)) |
C#
using System;class GFG { // Function to find the number of integers // less than or equal to N with no // consecutive 1’s in binary representation static int FindIntegers(int num) { // Convert N to binary form string bin = ""; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2 == 1) bin += "1"; else bin += "0"; num /= 2; } char[] binArray = bin.ToCharArray(); Array.Reverse(binArray); bin = new string(binArray); int n = bin.Length; // DP table to store the solutions int[][][] dp = new int[n + 1][][]; for (int i = 0; i <= n; i++) { dp[i] = new int[2][]; for (int j = 0; j < 2; j++) { dp[i][j] = new int[2]; for (int k = 0; k < 2; k++) { dp[i][j][k] = 0; } } } // Initializing the DP table dp[0][0][0] = 1; // Loop through each digit for (int i = 1; i <= n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { int limit = (j == 1) ? 1 : (bin[i - 1] - '0'); for (int l = 0; l <= limit; l++) { if (l == 1 && k == 1) continue; dp[i][j | ((l < limit) ? 1 : 0)][l] += dp[i - 1][j][k]; } } } } // Calculating the result int result = 0; for (int i = 0; i < 2; i++) { result += dp[n][i][0]; result += dp[n][i][1]; } return result; } // Driver code public static void Main(string[] args) { int N = 12; Console.WriteLine(FindIntegers(N)); }} |
Javascript
// Javascript function to find the number of integers// less than or equal to N with no// consecutive 1’s in binary representationfunction findIntegers(num) { // Convert N to binary form let bin = ""; // Loop to convert N // from Decimal to binary while (num > 0) { if (num % 2) bin += "1"; else bin += "0"; num = Math.floor(num / 2); } bin = bin.split("").reverse().join(""); let n = bin.length; // DP table to store the solutions let dp = []; for (let i = 0; i <= n; i++) { dp[i] = []; for (let j = 0; j < 2; j++) { dp[i][j] = []; for (let k = 0; k < 2; k++) { dp[i][j][k] = 0; } } } // Initializing the DP table dp[0][0][0] = 1; // Loop through each digit for (let i = 1; i <= n; i++) { for (let j = 0; j < 2; j++) { for (let k = 0; k < 2; k++) { let limit = (j ? 1 : parseInt(bin[i - 1])); for (let l = 0; l <= limit; l++) { if (l == 1 && k == 1) continue; dp[i][j | (l < limit)][l] += dp[i - 1][j][k]; } } } } // Calculating the result let result = 0; for (let i = 0; i < 2; i++) { result += dp[n][i][0]; result += dp[n][i][1]; } // return the final answer return result;}// Driver codelet N = 12;console.log(findIntegers(N)); |
Output
8
Time complexity: O(log N)
Auxiliary space: O(log N)
Explanation :
- The time complexity of the given code is O(log N), where N is the given input number. This is because the code loops through each digit of the binary representation of N, which has log N digits.
- The space complexity of the given code is O(log N), as well. This is because the code uses a DP table of size n+1 x 2 x 2, where n is the number of digits in the binary representation of N (i.e., log N). Since each element in the table is an integer, the total space used by the DP table is O(log 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!
