Q:

# 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.

```Result = f(0,1,n) + f(1,1,n)
```

The function arguments are,

```f(last,index,length)
```

Where last is the last digit, index is the current index and length is the sequence length.

So, we have two choice initially,

1. Put 0 at the 0th index and recur for rest of the length, thus last is 0 and index is 1
2. Put 1 at the 1st index and recur for rest of the length, thus last is 1 and index is 1

Below is the details of the recursive function

int MOD=1000000007

```Function f(int last ,int index,int length)
// base case
if(i==n)
return 1;

if(last==0 )
then we can both use 0 and 1 as our current digit, so,
return (f(0,index+1,n)%MOD + f(1,index+1,n)%MOD)%MOD;
else
only placing 0 is feasible since we can't allow contiguous 1
return f(0,index+1,n)%MOD;
End Function
```

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:

``````#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
int dp[101][2];

long long int myrecur(int i, int last, int n)
{
// base case
if (i >= n)
return 1;

// memoization by not computing the
if (dp[i][last] != -1)
return dp[i][last];

// store subproblem results
if (last == 0) {
dp[i][last] = (myrecur(i + 1, 0, n) % MOD + myrecur(i + 1, 1, n) % MOD) % MOD;
}
else {
dp[i][last] = myrecur(i + 1, 0, n) % MOD;
}

return dp[i][last];
}

long long int countofSequence(int n)
{
//initialize the dp store
for (int i = 0; i <= n; i++) {
dp[i][0] = -1;
dp[i][1] = -1;
}
return (myrecur(1, 0, n) % MOD + myrecur(1, 1, n) % MOD) % MOD;
}

int main()
{
int t, n, item;

cout << "Enter number of testcases\n";
cin >> t;

for (int i = 0; i < t; i++) {
cout << "Enter sequence length\n";
cin >> n;
cout << "Numbder of possible sequence is: " << countofSequence(n) << endl;
}

return 0;
}``````

Output:

```Enter number of testcases
3
Enter sequence length
3
Numbder of possible sequence is: 5
Enter sequence length
2
Numbder of possible sequence is: 3
Enter sequence length
55
Numbder of possible sequence is: 435293607```