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

# Generate all binary strings without consecutive 1’s

## 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' ;
stringsSizeKUtil ( K , s , 1 ) ;

//all strings starting with 1
s = '1' ;
stringsSizeKUtil ( K , s , 1 );
}

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

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