# 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.

## Leave a Reply