Binary Strings Without Consecutive 1's

Moderate
0/80
profile
Contributed by
7 upvotes
Asked in companies
MicrosoftMorgan StanleySnapdeal Ltd.

Problem statement

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1
Sample Output 1 :
5
2
Explanation For Sample Input 1 :
For test case 1 :
We will print 5 because:
There are 5 possible binary strings of length equal to three that do not contain consecutive 1’s: “000”, “001”, “010”, “100” and “101”.

For test case 2 : 
We will print 2 because:
There are 2 possible binary strings of length equal to one that does not contain consecutive 1’s: “0” and “1”.
Sample Input 2 :
2
4
100
Sample Output 2 :
8
470199269
Hint

Try to think of a bottom-up approach, ie: placing the i’th bit when you have already calculated the answer for i-1’th bit.

Approaches (3)
Recursion

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 :

  1. Initialize a variable ‘ans’ equal to 0, this will store the final count of binary strings that don’t contain consecutive 1’s.
  2. 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.
  3. 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.
  4. Finally, return the modulo of the sum of initial calls made to the recursive function.
Time Complexity

O( 2 ^ N ), where N denotes the length of the binary string.

 

To calculate the current position we are making two recursive calls to the previous position, this leads to an exponential time complexity (consider the number of nodes in a binary tree of height equal to ‘N’ for reference).

Hence the time complexity is O( 2^N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Binary Strings Without Consecutive 1's
Full screen
Console