Count number of binary strings without consecutive 1's

Count number of binary strings without consecutive 1's: This a standard recursive problem which has been featured in Flipkart, Microsoft interviews.
Submitted by Radib Kar, on June 14, 2020

Problem statement:

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 contains 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 ≤ 100
1 ≤ N ≤ 1000

Example:

Number of test cases: 2

Test case 1:
Input:
N: 3

Output:
Number of valid binary sequence: 5

Test case 2:
Input: 
N: 2

Output:
Number of valid binary sequence: 3

Explanation:

Test case 1:
5 strings are (000, 001, 010, 100, 101)
O11, 110, 111 are not allowed.

Test case 2:
3 strings are (00, 01, 10)
11 is not allowed

Solution approach

We can solve the above problem by recursion. The idea is place '0' or '1' as the last character and recur for the remaining length. So, we will start by placing 0 as the first character and 1 as the first character.

Result = f(0,1,n) + f(1,1,n)

The function arguments are,

f(last,index,length)

Where last is the last digit, index is the current index and length is the sequence length.

So, we have two choice initially,

  1. Put 0 at the 0th index and recur for rest of the length, thus last is 0 and index is 1
  2. Put 1 at the 1st index and recur for rest of the length, thus last is 1 and index is 1

Below is the details of the recursive function

int MOD=1000000007

Function f(int last ,int index,int length)
    // base case
    if(i==n)
        return 1;
    
    if(last==0 )
        then we can both use 0 and 1 as our current digit, so,
        return (f(0,index+1,n)%MOD + f(1,index+1,n)%MOD)%MOD;   
    else 
        only placing 0 is feasible since we can't allow contiguous 1
        return f(0,index+1,n)%MOD;    
End Function

Since it will generate many over lapping sub-problems, we need to use Dynamic programming to store the already computed sub problems. Below is the memorization approach.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
int dp[101][2];

long long int myrecur(int i, int last, int n)
{
    // base case
    if (i >= n)
        return 1;

    // memoization by not computing the 
    // subproblems computed already
    if (dp[i][last] != -1) 
        return dp[i][last];

    // store subproblem results
    if (last == 0) {
        dp[i][last] = (myrecur(i + 1, 0, n) % MOD + myrecur(i + 1, 1, n) % MOD) % MOD;
    }
    else {
        dp[i][last] = myrecur(i + 1, 0, n) % MOD;
    }

    return dp[i][last];
}

long long int countofSequence(int n)
{
    //initialize the dp store
    for (int i = 0; i <= n; i++) {
        dp[i][0] = -1;
        dp[i][1] = -1;
    }
    return (myrecur(1, 0, n) % MOD + myrecur(1, 1, n) % MOD) % MOD;
}

int main()
{
    int t, n, item;
    
    cout << "Enter number of testcases\n";
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        cout << "Enter sequence length\n";
        cin >> n;
        cout << "Numbder of possible sequence is: " << countofSequence(n) << endl;
    }

    return 0;
}

Output:

Enter number of testcases
3
Enter sequence length
3
Numbder of possible sequence is: 5
Enter sequence length
2
Numbder of possible sequence is: 3
Enter sequence length
55
Numbder of possible sequence is: 435293607





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.