Binary Queue

Concepts Used:

Queues.

Difficulty Level:

Medium.

Problem Statement :

Given a number N, print all possible binary numbers with decimal values from 1 to N, but the catch is you have to do this using queue data structure and not recursion.

See original problem statement here

Test Case:

Input:
2
4
5

Output:
1 10 11 100
1 10 11 100 101

Solving Approach:

Bruteforce Approach:

  1. Run a loop from 1 to N and call decimal to binary inside the loop.
  2. Print all the binary numbers in a single line.

Efficient Approach(Using queue):

  1. Refer the data structures and algorithms in c++ and Create an empty queue of strings.
  2. Enqueue 1,since it is the first binary number.
  3. Deque the value a and print it.
  4. Initialize string temp with a.
  5. Append "0" to string a and enqueue it to the queue.
  6. Append "1" to string temp and enqueue it to the queue.
  7. Repeat steps 3 to 8 until the end value.

Solutions

#include <stdio.h>
#include <string.h>
#define MAX 10005
char queue[MAX][20], temp[20];
int front = -1, rear = -1;
void enqueue(char *ptr)
   {
if(rear == MAX-1)
{
    return;
}
if(front == -1 && rear == -1)
    front = rear = 0;
else
    rear = rear + 1;
strcpy(queue[rear],ptr);
}
char* dequeue()
{
if(front == -1)
    printf("\nEmpty Queue");
else
{
    strcpy(temp,queue[front]);
    if(front == rear)
        front = rear = -1;
    else
        front = front + 1;
    return temp;
}
}
 void binary_numbers_using_queue()
{
char temp2[MAX];
strcpy(temp,dequeue());
printf("%s ",temp);
strcpy(temp2,temp);
strcat(temp,"0");
enqueue(temp);
strcat(temp2,"1");
enqueue(temp2);
}
 int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int n;scanf("%d",&n);
char temp[2] = "1";
enqueue(temp);
for(int i = 1; i <= n; i++)
    binary_numbers_using_queue();
    printf("\n");
    front = -1, rear = -1;
    for(int i=0;i<10005;i++)
    for(int j=0;j<20;j++)
    queue[i][j]='\0';
}
return 0;
}
#include <bits/stdc++.h> 
using namespace std; 
void binary(int n) 
{ 
queue<string> q; 
q.push("1"); 
while (n--) 
{  
    string a = q.front(); 
    q.pop(); 
    cout << a << " "; 
    string temp = a;  
    q.push(a.append("0"));
    q.push(temp.append("1")); 
} 
}  
int main() 
{ int t;cin>>t;
while(t--)
{int n ; 
cin>>n;
binary(n);
cout<<"\n";}
return 0; 
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class BinaryQueue {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t-->0)
    {
        int n= sc.nextInt();
        generateAndPrint(n);
        System.out.println();
    }
}
private static void generateAndPrint(int n) {
    Queue<String> queue = new LinkedList<String>();
    ((LinkedList<String>) queue).add("1");
    while (n-- >0)
    {
        String s1 = queue.peek();
        queue.remove();
        System.out.print(s1+" ");
        String s2 = s1;
        ((LinkedList<String>) queue).add(s1 + "0");
        ((LinkedList<String>) queue).add(s2+"1");
    }
}
}
Previous post Enqueue and Dequeue
Next post Swap Sum

Leave a Reply

Your email address will not be published. Required fields are marked *