# Count Binary Strings Without Consecutive Ones

## Count Binary Strings Without Consecutive Ones

In Count Binary Strings Without Consecutive Ones problem we have to count strings of length n such that each character of the string can only be 1 or 0. And we should not count strings with ’11’ as a sub string. Here is a C++ implementation of both top down and bottom up approach. ## Count Binary Strings Without Consecutive Ones Problem Statement

Given an integer n return the number of binary strings of length n such that they do not contain ’11’ as a sub string. The answer can be large so return the result modulo 1000000007.

Example:

Given n = 3

Output:

5

Explanation

The length 3 possible binary strings are – 000, 001, 010, 011, 100, 101 , 110, 111

Out of these 011, 110 and 111 contain 11 as a sub string. Therefore the result is 5.

## Count Binary Strings Without Consecutive Ones Solution

### Solution 1 (Top Down dynamic programming)

For writing the top down solution we will write a function F(id , prev).

F(id , prev) means number of binary strings of length n with prev filled at (n+1)th place. Now we have to decide our transitions.

The transitions will be :-

f(n,prev) = f(n-1,0)   + f(n-1,1) if(prev ==0)

or

f(n,prev) = f(n-1,0)                    if(prev==1)

We will be using a memo table to speed up the solution and avoid recalculation of values.

### C++ Code

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
ll memo;
ll solve(int nint prev)
{
if (n == 0)
return 1;
if (memo[n][prev] != –1)
return memo[n][prev];

ll op1 = 0op2 = 0;
op1 = solve(n – 10);
if (prev != 1)
op2 = solve(n – 11);
return memo[n][prev] = (op1 + op2) % MOD;
}
int main()
{
memset(memo, –1, sizeof memo);
int n;
cin >> n;
cout << solve(n0<< endl;

return 0;
}

`23`

### Solution 2 (Bottom up Dynamic Programming)

For writing bottom up dp solution we will create a dp table  as dp[n+1].

dp[i] gives us the count of binary strings of length i with ith charactor filled 0. dp[i] = dp[i-1] + dp[i-1]

dp[i] gives us the count of binary strings of length i with ith charactor filled 1. dp[i]  – dp[i-1] (Because we don’t need consecutive ones).

### C++ Code

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
ll solve(int n)
{
ll dp[n + 1];

dp = 1;
dp = 1;

for (int i = 2i <= ni++)
{
dp[i] = (dp[i – 1] + dp[i – 1]) % MOD;
dp[i] = (dp[i – 1]);
}
return (dp[n] + dp[n]) % MOD;
}
int main()
{
int n;
cin >> n;
cout << solve(n<< endl;
return 0;
}

`35`