Print all binary strings without consecutive 1s
The problem at hand is to generate and print all binary strings of a given length 'k' without consecutive 1s. In other words, we want to find all possible binary strings of length 'k' where no two consecutive characters are '1'. For instance, if k = 3, the valid binary strings would be "000", "001", "010", and "100".
Problem Statement and Description
The problem is to generate and display all binary strings of length 'k' without consecutive 1s. This means that any valid binary string should not contain consecutive '1's. For example, if k = 4, valid strings include "0000", "0010", "0100", and "1000", while "1100" and "0110" are not valid since they contain consecutive '1's.
Example
Let's take a small example to understand the problem better. Suppose k = 3. We want to generate and print all valid binary strings of length 3.
Valid binary strings: "000", "001", "010", "100".
Invalid binary strings: "110", "011", "101", "111".
Idea to Solve
To solve this problem, we can use a recursive approach. We will start building the binary string from left to right, and at each position, we can either place '0' or '1' based on the condition that there should be no consecutive '1's. We will keep track of the generated binary string using an array and pass this array to the recursive function.
Pseudocode
Here's the pseudocode for the solution:
function generateBinaryStrings(record[], start, k):
if start == k:
print record
return
record[start] = '0'
generateBinaryStrings(record, start + 1, k)
if record[start - 1] != '1':
record[start] = '1'
generateBinaryStrings(record, start + 1, k)
function binaryStrings(k):
if k <= 0:
return
record = array of size k
record[0] = '0'
generateBinaryStrings(record, 1, k)
record[0] = '1'
generateBinaryStrings(record, 1, k)
Algorithm Explanation
-
Define a recursive function
generateBinaryStrings(record[], start, k)
that takes three parameters: the arrayrecord
to store the generated binary string, thestart
position where we're currently placing the digit, andk
which is the length of the binary string. -
Inside
generateBinaryStrings
, ifstart
reachesk
, we have successfully generated a binary string of lengthk
without consecutive '1's, so we print it. -
Assign '0' to
record[start]
and recursively callgenerateBinaryStrings
withstart + 1
. -
Next, check if the previous digit
record[start - 1]
is not '1'. If it's not, then we can assign '1' torecord[start]
and recursively callgenerateBinaryStrings
withstart + 1
. -
Define the
binaryStrings(k)
function which acts as a wrapper. Ifk
is less than or equal to 0, there's no valid string to generate, so we return. -
Initialize the
record
array of sizek
and start with '0' at the first position. CallgenerateBinaryStrings(record, 1, k)
to generate valid binary strings starting with '0'. -
Change the first digit to '1' and again call
generateBinaryStrings(record, 1, k)
to generate valid binary strings starting with '1'.
Code Solution
/*
C program for
Print all binary strings without consecutive 1s
*/
#include <stdio.h>
void solution(char record[], int start, int k)
{
if (start == k)
{
printf(" %s \n", record);
return;
}
if (record[start - 1] == '0')
{
record[start] = '0';
solution(record, start + 1, k);
// change to 1
record[start] = '1';
solution(record, start + 1, k);
}
if (record[start - 1] == '1')
{
record[start] = '0';
solution(record, start + 1, k);
}
}
void binaryString(int k)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Use to contain result
char record[k];
// Set initial 0
record[0] = '0';
// Display the result which is starting by zeros
solution(record, 1, k);
record[0] = '1';
// Display the result which is starting by 1s
solution(record, 1, k);
}
int main(int argc, char const *argv[])
{
// Test
binaryString(5);
return 0;
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
/*
Java program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
public void solution(String record, int start, int k)
{
if (start == k)
{
System.out.print(" " + record + " \n");
return;
}
if (record.charAt(start - 1) == '0')
{
solution(record + '0', start + 1, k);
solution(record + '1', start + 1, k);
}
if (record.charAt(start - 1) == '1')
{
solution(record + '0', start + 1, k);
}
}
public void withoutConsecutive1s(int k)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
solution("0", 1, k);
// Display the result which is starting by 1s
solution("1", 1, k);
}
public static void main(String[] args)
{
BinaryText task = new BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
public: void solution(string record, int start, int k)
{
if (start == k)
{
cout << " " << record << " \n";
return;
}
if (record[start - 1] == '0')
{
this->solution(record + '0', start + 1, k);
this->solution(record + '1', start + 1, k);
}
if (record[start - 1] == '1')
{
this->solution(record + '0', start + 1, k);
}
}
void withoutConsecutive1s(int k)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
this->solution("0", 1, k);
// Display the result which is starting by 1s
this->solution("1", 1, k);
}
};
int main()
{
BinaryText *task = new BinaryText();
// Test k = 5
task->withoutConsecutive1s(5);
return 0;
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
// Include namespace system
using System;
/*
Csharp program for
Print all binary strings without consecutive 1s
*/
public class BinaryText
{
public void solution(String record, int start, int k)
{
if (start == k)
{
Console.Write(" " + record + " \n");
return;
}
if (record[start - 1] == '0')
{
this.solution(record + '0', start + 1, k);
this.solution(record + '1', start + 1, k);
}
if (record[start - 1] == '1')
{
this.solution(record + '0', start + 1, k);
}
}
public void withoutConsecutive1s(int k)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
this.solution("0", 1, k);
// Display the result which is starting by 1s
this.solution("1", 1, k);
}
public static void Main(String[] args)
{
BinaryText task = new BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
package main
import "fmt"
/*
Go program for
Print all binary strings without consecutive 1s
*/
func solution(record string, start int, k int) {
if start == k {
fmt.Print(" ", record, " \n")
return
}
if record[start - 1] == '0' {
solution(record + "0", start + 1, k)
solution(record + "1", start + 1, k)
}
if record[start - 1] == '1' {
solution(record + "0", start + 1, k)
}
}
func withoutConsecutive1s(k int) {
// K indicate digit in binary
if k <= 0 {
return
}
// Display the result which is starting by zeros
solution("0", 1, k)
// Display the result which is starting by 1s
solution("1", 1, k)
}
func main() {
// Test k = 5
withoutConsecutive1s(5)
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
<?php
/*
Php program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
public function solution($record, $start, $k)
{
if ($start == $k)
{
echo(" ".$record.
" \n");
return;
}
if ($record[$start - 1] == '0')
{
$this->solution($record.strval('0'), $start + 1, $k);
$this->solution($record.strval('1'), $start + 1, $k);
}
if ($record[$start - 1] == '1')
{
$this->solution($record.strval('0'), $start + 1, $k);
}
}
public function withoutConsecutive1s($k)
{
// K indicate digit in binary
if ($k <= 0)
{
return;
}
// Display the result which is starting by zeros
$this->solution("0", 1, $k);
// Display the result which is starting by 1s
$this->solution("1", 1, $k);
}
}
function main()
{
$task = new BinaryText();
// Test k = 5
$task->withoutConsecutive1s(5);
}
main();
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
/*
Node JS program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
solution(record, start, k)
{
if (start == k)
{
process.stdout.write(" " + record + " \n");
return;
}
if (record.charAt(start - 1) == '0')
{
this.solution(record + '0', start + 1, k);
this.solution(record + '1', start + 1, k);
}
if (record.charAt(start - 1) == '1')
{
this.solution(record + '0', start + 1, k);
}
}
withoutConsecutive1s(k)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
this.solution("0", 1, k);
// Display the result which is starting by 1s
this.solution("1", 1, k);
}
}
function main()
{
var task = new BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
main();
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
# Python 3 program for
# Print all binary strings without consecutive 1s
class BinaryText :
def solution(self, record, start, k) :
if (start == k) :
print(" ", record ," ")
return
if (record[start - 1] == '0') :
self.solution(record + str('0'), start + 1, k)
self.solution(record + str('1'), start + 1, k)
if (record[start - 1] == '1') :
self.solution(record + str('0'), start + 1, k)
def withoutConsecutive1s(self, k) :
# K indicate digit in binary
if (k <= 0) :
return
# Display the result which is starting by zeros
self.solution("0", 1, k)
# Display the result which is starting by 1s
self.solution("1", 1, k)
def main() :
task = BinaryText()
# Test k = 5
task.withoutConsecutive1s(5)
if __name__ == "__main__": main()
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
# Ruby program for
# Print all binary strings without consecutive 1s
class BinaryText
def solution(record, start, k)
if (start == k)
print(" ", record ," \n")
return
end
if (record[start - 1] == '0')
self.solution(record + '0'.to_s, start + 1, k)
self.solution(record + '1'.to_s, start + 1, k)
end
if (record[start - 1] == '1')
self.solution(record + '0'.to_s, start + 1, k)
end
end
def withoutConsecutive1s(k)
# K indicate digit in binary
if (k <= 0)
return
end
# Display the result which is starting by zeros
self.solution("0", 1, k)
# Display the result which is starting by 1s
self.solution("1", 1, k)
end
end
def main()
task = BinaryText.new()
# Test k = 5
task.withoutConsecutive1s(5)
end
main()
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
import scala.collection.mutable._;
/*
Scala program for
Print all binary strings without consecutive 1s
*/
class BinaryText()
{
def solution(record: String, start: Int, k: Int): Unit = {
if (start == k)
{
print(" " + record + " \n");
return;
}
if (record.charAt(start - 1) == '0')
{
solution(record + '0'.toString(), start + 1, k);
solution(record + '1'.toString(), start + 1, k);
}
if (record.charAt(start - 1) == '1')
{
solution(record + '0'.toString(), start + 1, k);
}
}
def withoutConsecutive1s(k: Int): Unit = {
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
solution("0", 1, k);
// Display the result which is starting by 1s
solution("1", 1, k);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinaryText = new BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
import Foundation;
/*
Swift 4 program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
func solution(_ record: String, _ start: Int, _ k: Int,_ back : String)
{
if (start == k)
{
print(" ", record ," ");
return;
}
if (back == "0")
{
self.solution(record + "0", start + 1, k,"0");
self.solution(record + "1", start + 1, k,"1");
}
if (back == "1")
{
self.solution(record + "0", start + 1, k,"0");
}
}
func withoutConsecutive1s(_ k: Int)
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
self.solution("0", 1, k,"0");
// Display the result which is starting by 1s
self.solution("1", 1, k,"1");
}
}
func main()
{
let task: BinaryText = BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
main();
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
/*
Kotlin program for
Print all binary strings without consecutive 1s
*/
class BinaryText
{
fun solution(record: String, start: Int, k: Int): Unit
{
if (start == k)
{
print(" " + record + " \n");
return;
}
if (record.get(start - 1) == '0')
{
this.solution(record + "0", start + 1, k);
this.solution(record + "1", start + 1, k);
}
if (record.get(start - 1) == '1')
{
this.solution(record + "0", start + 1, k);
}
}
fun withoutConsecutive1s(k: Int): Unit
{
// K indicate digit in binary
if (k <= 0)
{
return;
}
// Display the result which is starting by zeros
this.solution("0", 1, k);
// Display the result which is starting by 1s
this.solution("1", 1, k);
}
}
fun main(args: Array < String > ): Unit
{
val task: BinaryText = BinaryText();
// Test k = 5
task.withoutConsecutive1s(5);
}
Output
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
Time Complexity
The time complexity of this solution can be analyzed by considering the number of recursive calls. Each recursive call either places '0' or '1' at a specific position, and there are two possible choices at each step. The total number of recursive calls will be 2^k. Therefore, the time complexity is O(2^k), where k is the length of the binary string.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment