How to count number of binary strings without consecutive 1’s in Python

In this tutorial, we will focus on counting the number of binary strings that do not consist of consecutive ones in the binary format in Python.

Let’s use an example for a better understanding and build an analytical approach to solve this task.

Example and approach

Take any input n.

We will take 3 as input.

We will append zeros and ones to the binary strings available.

Let’s consider binary strings

When n=1.

Binary strings would be 0,1

When n=2, we can either append 0 or 1 to these strings.

The resulting string after appending would be: 00,10,01,11 here we will only consider 3 strings because 11 has consecutive ones.

Output when n=2 should be 3 which are 00,10,01.

When n=3, again we can either append 0 or 1 to these strings.

Appending 1 to the string ending with 1 would result in consecutive ones, which is a negligible case.

For building a logical approach we can divide these strings into two parts, namely zeroending, and oneending which will hold the value of the number of strings ending at zeroes, and ones which will be 2 and 1 respectively.

To the above-mentioned 3 binary strings, we can append 0 and 1 but to that string ending with one, we can only append 0 not 1 to avoid the negligible case.

The resulting strings would be: 000,100,010,001,101, and 011 will be ignored which is that one string from oneending. So here we have zeroending as 3 and onending as 2.

So when n=3, the output will be 3+2=5.

Logical approach-

When n=2

0      00,01

1       10,11-> Discard 11

zeroending– {00,10}- 2 elements

oneending – {01}- 1 element

sum=zeroending+oneending=2+1=3

When n=3

00,10       000,100,001,101

01             010,111->Discard 111

zeroending– {000,100,010}-3 elements

oneending– {001,101}- 2 elements

sum=3+2=5

When n=4

000,100,010       0000,1000,0100,0001,1001,0101

001,101                0010,1010,0011,1011->Discard 0011,1011

zeroending– {0000,1000,0100,0010,1010}-5 elements

oneending– {0001,1001,0101}- 3 elements

sum=5+3=8

So, we can observe that number of elements in sum becomes zero ending and that of zero ending becomes one ending when we append zeroes and ones.

We can iterate over i such that, until it is less than n, we need to shift the zeroending to oneending, and sum to zeroending and the base case would be when n=1, return sum which is 1+1=2.

Python Code to count number of binary strings without consecutive 1’s

As we have already discussed the logical approach, here’s the implementation part-

def countStrings(n):
      zeroending=1
      oneending=1
      sum=zeroending+oneending
      if n==1:
          return sum
      i=2
      while(i<=n):
          oneending=zeroending
          zeroending=sum
          sum=zeroending+oneending
          i+=1
      return sum%1000000007
n=3
print(countStrings(n))

Output:

5

So we have implemented the above approach and we have completed our task to print the number of binary strings given any integer n which do not contain consecutive ones.