Binary strings with no consecutive 1s.
You have been given an integer K.

Your task is to generate all binary strings of length K such that there are no consecutive 1s in the string. This means that the binary string should not contain any instance of 1’s coming one after another.

A binary string is that string which contains only ‘0’ and ‘1’.

For Example:

Let ‘K=3’, hence the length of the binary string would be 3. We can have the following binary strings with no consecutive 1s: 000 001 010 100 101

Note

1. Each string must be a binary string. 2. There should be no consecutive ‘1’ in the string. 3. Return an array/sequence of all the strings in an array in a lexicographically increasing order.

Input format:

The first line of input contains ‘T’ the number of test cases. The first and only line of each test case contains a single integer K denoting the length of the binary string to be generated.

Output Format

For each test case, print all possible binary strings without consecutive ‘1’ of the length K in lexicographically increasing order.

Note:

You don't need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Binary strings with no consecutive 1s.

You have been given an integer K.

Your task is to generate all binary strings of length K such that there are no consecutive 1s in the string. This means that the binary string should not contain any instance of 1’s coming one after another.

A binary string is that string which contains only ‘0’ and ‘1’.

For Example:

Let ‘K=3’, hence the length of the binary string would be 3. We can have the following binary strings with no consecutive 1s:
000 001 010 100 101

Note

1. Each string must be a binary string.
2. There should be no consecutive ‘1’ in the string.
3. Return an array/sequence of all the strings in an array in a lexicographically increasing order.

Input format:

The first line of input contains ‘T’ the number of test cases.

The first and only line of each test case contains a single integer K denoting the length of the binary string to be generated.

Output Format

For each test case, print all possible binary strings without consecutive ‘1’ of the length K in lexicographically increasing order.

Note:

You don't need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
0 <= K <= 22

Time limit: 1 second

Accepted Answer

You can easily observe pattern. It is a Fibonacci sequence

Accepted Answer

Recursive Approach

Since we need to generate all substring which does not have consecutive 1s we can simply start adding new characters to the string until the length of the string is ‘K’ taking care that if the last character of the current string is ‘1’ we cannot add another ‘1’ as it will result in consecutive ‘1s.’ Otherwise, if the last character is ‘0’ we have 2 options either to add ‘1’ or ‘0’. We explore both the options recursively until we have a string of desired length i.e ‘K’ .

We start with a string of length 1. Now we have 2 options, the first character can be a ‘1’ or a ‘0’.
We take both possibilities and use our recursive function to find the answer.

For example, let’s say that ‘K’=3 and the first character is ‘0’.

We see that we get 3 unique strings for starting character ‘0’.

In a similar way, we will get all possible strings of length ‘3’ for strings starting with 1.

Our recursive function works as follows:

Check the last character of the string. If the last character is ‘0’ we can add a ‘0’ or ‘1’ at the end of the string.
If the last character is ‘1’ we can add only ‘0’ and not ‘1’ because if we add ‘1’ and the last character is also ‘1’ we will violate the condition that there must be no consecutive ‘1’ in the string.
Once the length of the string is equal to ‘K’ we add it to our answer array.
Lastly, we sort the array and return all possible strings of length ‘K’ with no consecutive ‘1’.

Following is the detailed order in which the recursion calls occur for length 3:

Space Complexity: O(n)Explanation:

O(N), ‘N’ is the length of the string

The recursive stack uses space of the order O(N).

Time Complexity: O(2^n)Explanation:

O(2 ^ N), ‘N’ is the length of the string.

For every character, we have 2 choices either put a ‘0’ or a ‘1’ hence for ‘N’ choices we will have a total time complexity of order of O(2 ^ N)