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] ;
}
---------------------------------------------------------------------------------
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
Post a Comment