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.

Read more about Recursion: Recursion in Python

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! 😇