Count number of binary strings without consecutive 1's
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1's. Output your answer mod 10^9 + 7.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains an integer N representing length of the binary string.
Output:
Print the count number of binary strings without consecutive 1's of length N.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
Example:
Number of test cases: 2
Test case 1:
Input:
N: 3
Output:
Number of valid binary sequence: 5
Test case 2:
Input:
N: 2
Output:
Number of valid binary sequence: 3
Explanation:
Test case 1:
5 strings are (000, 001, 010, 100, 101)
O11, 110, 111 are not allowed.
Test case 2:
3 strings are (00, 01, 10)
11 is not allowed
We can solve the above problem by recursion. The idea is place '0' or '1' as the last character and recur for the remaining length. So, we will start by placing 0 as the first character and 1 as the first character.
The function arguments are,
Where last is the last digit, index is the current index and length is the sequence length.
So, we have two choice initially,
Below is the details of the recursive function
int MOD=1000000007
Since it will generate many over lapping sub-problems, we need to use Dynamic programming to store the already computed sub problems. Below is the memorization approach.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer