# Find Number of Possible Strings With No Consecutive 1s In this tutorial, we will be understanding a very interesting problem known as Forming a string with no consecutive 1s. Let us first understand what do we want to achieve in this problem.

We have an integer n that is the size of the string i.e. the number of bits in the final string.

Our aim is to get the string having n bits with no consecutive 1 which means: `11` is illegal in the string.

Now for any string, there can be two cases:
If the first element is 0 then the next element can be either 0 or 1.
In the other case i.e. the first element is 1 then the only choice we have for the next element is 0.

Our aim is to find the count of all such possible strings which satisfy the condition mentioned above.

## How to find the number of possible strings without consecutive 1s?

The problem can be solved in a manual way or through the recursion approach. The recursion approach is a better, more efficient, and faster technique to solve the problem.

If you want to know more about recursion read the tutorial mentioned below.

The two cases are as follows:

• First digit is 1 then we set the second bit as 0 and check for n-2 places left in the final string.
• First digit is 0 then we check for n-1 places left in the string

First, let us look at the answer for lower values of n starting from 0.

For all the cases where n is greater than 2, we will be considering the two cases.

## Implementing the Recursion in Python

```def count_no_ways(n):
if(n==0):
return 0
if(n<3):
return n+1
return count_no_ways(n-1) + count_no_ways(n-2)

n = int(input())
print(count_no_ways(n))
```

Output:

10
144

I hope by end of this tutorial, I hope you understood the problem, solution, and code implementation of the solution.

Thank you for reading! Happy learning! 😇