Count of binary strings without consecutive 1’s

Tags: ,

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example,

Input:
N = 2
Output:
3.
Explanation:
There are 3 possible strings: 00, 01, 10
N=3
There are 5 possible strings: 000, 001, 010, 100,101

Thought process to find binary strings with consecutive 1s

This problem is an easier variation of digit DP problem. Since these are binary strings for every position in the string there are just two choices: 0 and 1. To form a string of length N, at any position –

  1. We can choose 0 and then for the next position we again have two choices.
  2. We can choose 1 but then for the next position we cannot choose 1 as we don’t want consecutive 1’s in the string. So once we choose 1, we are also setting next position to 0.

So in case (a), we set 0 at current position and the problem then reduces to count the number of strings having length N-1 with the given condition.

And in case (b), we set 1 at current position and 0 at next position, hence the problem reduces to count the number of strings having length N-2 with the given condition.

With this we can write

Count(n) = Count(n-1) + Count(n-2)

Does this formula ring a bell? Yes, it’s the same one that is is used to find Fibonacci numbers.

As Count(1) = 2, Count(2) = 3, Count(3) = 5, ……
and Fib(1) = 1,  Fib(2) = 1, Fib(3) = 2, Fib(3) = 3, Fib(4) = 5, ……

Hence we can observe that-
Count(n) = Fib(n+2)

Using the explanation for DP approach and the implementation in Find Nth Fibonacci number problem:

#include <iostream>
#include <vector>
using namespace std;

long long int fib(int N)
{
    vector<long long int> DPVec(N+1, 0);
    DPVec[1] = 1; DPVec[2] = 1;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2];
    }
   return DPVec[N];
}

long long int Cnt_strings(int N)
{
    return fib(N+2);
}

int main()
{
    int n = 3;
    cout<<Cnt_strings(n)<<endl;
    return 0;
}
public class Count_Strings
{
    static int fib(int N)
    {
        int DPArr[] = new int[N+1];
        DPArr[1] = 1; DPArr[2] = 1;
        for (int i=3; i&lt;=N; ++i)
        {
            DPArr[i] = DPArr[i-1] + DPArr[i-2];
        }
        return DPArr[N];
    }
       
    static int Cnt_strings(int N)
    {
        return fib(N+2);
    }
    
    public static void main (String[] args) 
    {
	int n = 4;
	int num_strings = Cnt_strings(n);
	System.out.println(num_strings);
    }
}
The time complexity of the implementation is O(n) and space complexity is also O(n)