Consecutive 1's not allowed

PROBLEM :
Count number of binary strings without consecutive 1’s

Problem Description:
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s. Output your answer mod 10^9 + 7.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contain an integer N representing length of the binary string.

Output:
Print the count number of binary strings without consecutive 1’s of length N.

Constraints:
1 = T = 10
1 = N = 70

Example:
Input:
2
3
2

Output:
5
3

Explaination:
For first test case 5 strings are (000, 001, 010, 100, 101)
For second test case 3 strings are (00,01,10)

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
int Consecutive1s_notAllow(int ) ;
int main()
{
int t,no ;
cin>>t ;
while(t--)
{
   cin>>no ;
   cout<<Consecutive1s_notAllow(no)<<endl ;
}
return 0;
}

int Consecutive1s_notAllow(int no)
{
    int i ;
    int arr[no+1] ;
   
    arr[0]=1 ;
    arr[1]=2 ;
   
    for(i=2;i<=no;i++)
        arr[i]=(arr[i-1]+arr[i-2])%1000000007 ;
       
    return arr[no] ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )