# Find all N-digit binary strings without any consecutive 1’s

Given a positive integer N, count all N-digit binary strings without any consecutive 1’s.

For example, for N = 5 the binary strings satisfies the given constraints are

00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101

A simple solution would be to generate all N-digit strings and print only those strings that satisfies the given constraints. The complexity of this solution would be exponential.

A better solution would be to generate only those N-digit strings that satisfies the given constraints. The idea is to use recursion. At each point in the recursion, we append 0 and 1 to the partially formed number and recurse with one less digit. The trick here is that we append 1 and recurse only if last digit of partially formed number is 0. That way, we will never have any consecutive 1’s in output string.

Below is C++ and Java implementation of the idea:

## Java

Output:

Number of 5-digit binary strings without any consecutive 1’s are 13

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The problem has an optimal substructure and also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by using dynamic programming, in which subproblem solutions are memoized rather than computed again and again.

The bottom-up approach is illustrated below where we solve smaller sub-problems first, then solve larger sub-problems from them.

Below is C++ and Java implementation of the idea:

## C++

Output:

Number of 5-digit binary strings without any consecutive 1’s are 13

## Java

Output:

Number of 5-digit binary strings without any consecutive 1’s are 13

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

### How to print all binary strings?

Below recursive code prints all binary strings as well.

## Java

Output:

00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

You can optimize your DP scheme to store only the last row of the table. You can also prove the number of such strings has a direct relation to Fibonacci numbers that can be computed in O(log(n)) time. Guest

my solution:
int count(int n)
{
if (n == 1)
return 2;
if (n == 0)
return 1;
return count(n – 2) + count(n – 1);
}
the main idea is : if you chose the current is 1,move 2 step or choose 0 move 1 step.Base case if n=1
there are TWO solution, if n=0 there’re ONE solution
also dynamic approach will take one single array