Last Updated: 19 Nov, 2021
Binary Strings Without Consecutive 1's
Moderate
Asked in companies
You are given an integer ‘N’, you need to find the count of binary strings of length equal to ‘N’ that do not contain consecutive 1’s. As the answer can be large, print its value modulo 10^9 + 7.
Follow up :
Can you try to solve this problem in O(N) time and O(1) space?
Example :
If ‘N’ = 3
Then there are 5 possible binary strings of length equal to 3 that do not contain consecutive 1’s: “000”, “001”, “010”, “100”, “101”.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the length of the binary string(s).
Output Format :
For each test case, print the count of possible binary strings of length equal to ‘N’ that do not contain consecutive 1’s.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 20000
Time limit: 1 sec
Approaches
There are 2^N binary strings possible of length equal to N, we can recursively generate all possible binary strings, we can even prune this search by using a standard backtracking technique and generate only the strings that satisfy the given condition, but in this approach, we will discuss something that is bottom-up in nature and can later be extended to memoize results and become an efficient dynamic programming solution, but for this solution, we will limit our discussion to just a simple recursion.
For each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when i-1’th position doesn’t contain a 1, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the number of strings formed by placing either a 0 or a 1 at the i-1’th position. This creates a perfect recursive approach as we are recalculating things in a similar way for each of the positions in the binary string.
The steps are as follows :
- Initialize a variable ‘ans’ equal to 0, this will store the final count of binary strings that don’t contain consecutive 1’s.
- Make initial calls to the recursive function, in the first call pass the last position and 0-bit as parameters, and in the second call pass the last position and 1-bit as parameters.
- The first call returns the number of binary strings of length equal to ‘N’ that have 0 as their last bit and don’t contain consecutive 1’s.
- The second call returns the number of binary strings of length equal to ‘N’ that have 1 as their last bit and don’t contain consecutive 1’s.
- We will later return the modulo of the sum of these calls.
- In the recursive function:
- Declare a base condition to end the recursion: if the current index ‘idx’ is equal to 0, then return the value equal to 1. This is because the number of binary strings of length equal to one that ends with a particular digit will be equal to 1, therefore we are returning a value 1 when ‘idx’ equals 0.
- If the current bit to be placed ‘curBit’ is equal to 0, then make recursive calls to the previous index passing ‘curBit’ equal to 0 in one call, and ‘curBit’ equal to 1 in the other call. Return the modulo of sum of these two recursive calls.
- If the current bit to be placed ‘curBit’ is equal to 1, then make a single recursive call to the previous index passing ‘curBit’ equal to 0 and return the value returned from this recursive call.
- Finally, return the modulo of the sum of initial calls made to the recursive function.
For each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when i-1’th position doesn’t contain a 1, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the sum of the number of strings formed by placing either a 0 or a 1 at the i-1’th position. This creates a perfect recursive approach as we are recalculating things in a similar way for each of the positions in the binary string.
But we can avoid the recalculations if we use a dp-table to store the number of strings of length equal to ‘X’ ending with a 0-bit or a 1-bit. This way we won’t have to recalculate things and is a standard way to memoize recursive solutions and convert them into dynamic programming.
The steps are as follows :
- Initialize a variable ‘ans’ equal to 0, this will store the final count of binary strings that don’t contain consecutive 1’s.
- Declare a 2D array ‘dp’ of size N * 2, and initialize all the values equal to -1. Here, dp[i][j] denotes the count of binary strings of length equal to ‘i’ that have the last bit equal to ‘j’. Initialize dp[0][0] and dp[0][1] equal to 1 as base condition, this state denotes the binary string of length equal to one.
- Make initial calls to the recursive function, in the first call pass the last position and 0-bit as parameters, and in the second call pass the last position and 1-bit as parameters.
- The first call returns the number of binary strings of length equal to ‘N’ that have 0 as their last bit and don’t contain consecutive 1’s.
- The second call returns the number of binary strings of length equal to ‘N’ that have 1 as their last bit and don’t contain consecutive 1’s.
- We will later return the modulo of the sum of these calls.
- In the recursive function:
- Declare a base condition to end the recursion: if the current index ‘idx’ is equal to 0, then return the value equal to the value corresponding to the ‘dp’ matrix. This is because the number of binary strings of length equal to one that ends with a particular digit will be equal to 1, therefore we are returning a value 1 when ‘idx’ equals 0.
- If the value corresponding to the dp[idx][curBit] is not equal to -1, means we have already calculated this result and we will directly return it to avoid recalculation.
- If the current bit to be placed ‘curBit’ is equal to 0, then make recursive calls to the previous index passing ‘curBit’ equal to 0 in one call, and ‘curBit’ equal to 1 in the other call. Store the modulo of the sum of these two recursive calls in the ‘dp’ matrix.
- If the current bit to be placed ‘curBit’ is equal to 1, then make a single recursive call to the previous index passing ‘curBit’ equal to 0 and store the value returned from this recursive call in the ‘dp’ matrix.
- Finally return the value corresponding to dp[idx][curBit].
- Finally, return the modulo of the sum dp[N-1][0] and dp[N-1][1], as these values of the ‘dp’ matrix will include all the binary strings of length equal to ‘N’ that doesn’t contain consecutive 1’s.
For each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when the i-1’th position doesn’t contain a ‘1’, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the sum of the number of strings formed by placing either a 0 or a 1 at the i-1’th position.
Let’s define our dp states now, we can define dp[i][j] equal to the count of binary strings that are of length equal to ‘i’ and contain ‘j’ as the last bit. We can define transitions as dp[i][1] = dp[i-1][0] and dp[i][1] = dp[i-1][0] + dp[i-1][1]. A clever observation here is that we need not store all the dp results for ‘i’ equal to 0 to N - 1, rather we just need to store the results of the previous index which can be done with the help of just two variables. This will save a lot of space and convert a linear space solution to a constant space solution.
The steps are as follows :
- Initialize ‘prev0’ and ‘prev1’ equal to 1, they will store the count of binary strings ending at the previous index and having 0-bit and 1-bit respectively as their ending bits. Also declare variables ‘cur0’ and ‘cur1’.
- Run a FOR loop for variable ‘i’ from 2 to N, inside the loop:
- Update ‘cur0’ equal to prev0 + prev1.
- Update ‘cur1’ equal to prev0.
- Now, store ‘cur0’ in ‘prev0’ and store ‘cur1’ in ‘prev1’.
- Finally, return the sum of ‘cur0’ and ‘cur1’.
Similar problems