Last Updated on March 22, 2022 by Ria Pathak
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 101Solving Approach:
Bruteforce Approach:
- Run a loop from 1 to N and call decimal to binary inside the loop.
- Print all the binary numbers in a single line.
Efficient Approach(Using queue):
- Create an empty queue of strings.
- Enqueue 1,since it is the first binary number.
- Deque the value a and print it.
- Initialize string temp with a.
- Append "0" to string a and enqueue it to the queue.
- Append "1" to string temp and enqueue it to the queue.
- Repeat steps 3 to 8 until the end value.
Solutions
#include#include #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; }
#includeusing namespace std; void binary(int n) { queue 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 queue = new LinkedList();
((LinkedList) queue).add("1");
while (n-- >0)
{
String s1 = queue.peek();
queue.remove();
System.out.print(s1+" ");
String s2 = s1;
((LinkedList) queue).add(s1 + "0");
((LinkedList) queue).add(s2+"1");
}
}
}
def binary(n):
q = []
q.append("1")
while n:
n-=1
a = q[0]
q.pop(0)
print(a, end = " " )
temp = a
q.append(a + "0")
q.append(temp + "1")
for _ in range(int(input())):
n = int(input())
binary(n)
print()
[forminator_quiz id="1836"]
So, in this blog, we have tried to explain the concept of queue data sructure. If you want to solve more questions on Queues, which are curated by our expert mentors at PrepBytes, you can follow this link Queues.