Home » Technical Interview Questions » String Interview Questions » Generate all binary strings without consecutive 1’s

Generate all binary strings without consecutive 1’s


Reading Time - 1 mins

Given an integer k, write a function to print all binary strings of size k with no consecutive 1’s

Example

INPUT
k = 3

OUTPUT
“000”, “001”, “101”, “010”, “100”

Algorithm(recursive algo)

1. If size of the generated string becomes equal to the given size print the string.

2. If the previous character is ‘1’, the put ‘0’ at the end of the string and recursively call function
s[n] = ‘0’;
stringsSizeK(k, s, n+1)

3. If previous character is ‘0’, then put both ‘1’ and ‘0’ at end of string
s[n] = ‘0’
stringsSizeK(k, s, n+1)
s[n] = ‘1’
stringsSizeK(k, s, n+1)

C++ Program

#include <bits/stdc++.h>
using namespace std;
//Recursive function
void stringsSizeKUtil(int K, char s[], int n)
{
    // print if sizes are equal
    if (n  == K)
    {
        // terminate binary string
        s[n] = '\0' ;
        cout << s << " "<<endl;
        return ;
    }
 
    //If prev char is 1
    if (s[n-1] == '1')
    {
        s[n] = '0';
        stringsSizeKUtil (K , s , n+1);
    }
 
    //If prev char is 0
    if (s[n-1] == '0')
    {
        s[n] = '0';
        stringsSizeKUtil(K, s, n+1);
        s[n] = '1';
        stringsSizeKUtil(K, s, n+1) ;
    }
}
 
//main function
void stringsSizeK(int K )
{
    // Base case
    if (K <= 0)
        return ;
 
    // One by one stores every binary string of length K
    char s[K];
 
    //all strings starting with 0
    s[0] = '0' ;
    stringsSizeKUtil ( K , s , 1 ) ;
 
    //all strings starting with 1
    s[0] = '1' ;
    stringsSizeKUtil ( K , s , 1 );
}
 

int main()
{
    int K = 4;
    stringsSizeK (K) ;
    return 0;
}

Try It

 

READ  Find unique character in a string
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions