Home » Interview coding problems/challenges

# 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

*such that there are no consecutive 1's. Output your answer mod*

**N***10^9 + 7*

**.**

**Input:**

The first line of input contains an integer * T* denoting the number of test cases. The description of

*test cases follows.*

**T**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,

- Put 0 at the 0
^{th}index and recur for rest of the length, thus last is 0 and index is 1 - Put 1 at the 1
^{st}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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions