Generate all Binary Strings Without Consecutive 1’s

Difficulty Level Easy
Frequently asked in Amazon GE Healthcare Snapdeal Target Corporation
StringViews 4775

Problem Statement

In the “Generate all binary strings without consecutive 1’s” problem we have given an integer k, write a program to print all binary strings of size k with no consecutive 1’s.

Input Format

The first and only one line containing an integer N.

Output Format

Print all possible strings of length K separated by space(” “).

Constraints

  • 1<=N<=15

Example

4

0000 0001 0010 0100 0101 1000 1001 1010

Explanation: Here we first see all possible strings with length 4.

0: 0000

1: 0001

2: 0010

3: 0011

4: 0100

5: 0101

6: 0110

7: 0111

8: 1000

9: 1001

10: 1010

11: 1011

12: 1100

13: 1101

14: 1110

15: 1111

Now, we easily see 3, 6, 7, 11, 12, 13, 14, and 15 not follow the criteria because they all have consecutive 1’s. So, our final answer is 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010.

Algorithm

  • If the size of the generated string becomes equal to the given size print the string.
  • If the previous character is ‘1’, put ‘0’ at the end of the string and recursively call the function.
  1. s[n] = ‘0’.
  2. stringsSizeK(k, s, n+1)
  • If the previous character is ‘0’, then put both ‘1’ and ‘0’ at end of the string

1. s[n] = ‘0’
2. stringsSizeK(k, s, n+1)
3. s[n] = ‘1’
4. stringsSizeK(k, s, n+1)

  • If the length of the string is equal to K then print the string.

Implementation

C++ program to Generate all Binary Strings Without Consecutive 1’s

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

void strings_form(int K, char s[], int n)
{
    if(n==K)
    {
        s[n] = '\0' ;
        cout<<s<<" ";
        return;
    }
    if(s[n-1]=='1')
    {
        s[n]='0';
        strings_form(K,s,n+1);
    }
    if(s[n-1]=='0')
    {
        s[n]='0';
        strings_form(K,s,n+1);
        s[n]='1';
        strings_form(K,s,n+1) ;
    }
}
 
void print_strings(int K)
{
    if(K<=0)
    {
        return;
    }
    char s[K];
    s[0]='0' ;
    strings_form(K,s,1) ;
    s[0]='1';
    strings_form(K,s,1);
}
 
int main()
{
    int N;
    cin>>N;
    print_strings(N);
    return 0;
}

Java Program to Generate all Binary Strings Without Consecutive 1’s

import java.util.Scanner;

class sum {
    
    static void strings_form(int k, char s[], int n)
    {
        if(n==k)
        {
            s[n]='\0';
            System.out.print(s);
            System.out.print(" ");
            return;
        }
        if(s[n-1]=='1')
        {
            s[n]='0';
            strings_form(k,s,n+1);
        }
        if(s[n-1]=='0')
        {
            s[n]='0';
            strings_form(k,s,n+1);
            s[n]='1';
            strings_form(k,s,n+1);
        }
    }
    static void print_strings(int n) 
    {
        if(n<=0)
        {
            return;
        }
        char s[] = new char[n+1];
        s[0]= '0';
        strings_form(n,s,1);
        s[0]= '1';
        strings_form(n,s,1);
    }
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        int n = sr.nextInt();
        print_strings(n);
    } 
}
5
00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101

Complexity Analysis to Generate all Binary Strings Without Consecutive 1’s

Time Complexity

0(2^n) where n is the input number given to us which denotes the length of the string.

Space Complexity

o(n) where n is the input number given to us. Here we declare a char array to store the string.

Reference

Translate ยป