Generate Binary Numbers using Queue data structure

Generate Binary Numbers using Queue data structure

Problem Statement (from geeksforgeeks):

Given a number n, Write a program that generates and prints all binary numbers with decimal values from 1 to n.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N.

Output:

Print all binary numbers with decimal values from 1 to n in a single line.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 500

Example:

Input
2
2
5

Output
1 10
1 10 11 100 101

Solution:

/* Generating Binary Numbers of given input using Queue Data structure.

 * Implemented in C language.

 * Used Circular Queue as part of the implementation

 */

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct queue{

    int cap;

    int front, rear;

    int size;

    char array[1000][10];

};

struct queue* createQueue(int n){

    struct queue *q = (struct queue*)malloc(sizeof(struct queue));

    

    q->cap = n;

    q->front = -1;

    q->rear = n - 1;

    q->size = 0;

    return q;

}

int isQueueEmpty(struct queue *q){

    return q->size == 0;

}

int isQueueFull(struct queue *q){

    return q->size == q->cap;

}

void enQueue(struct queue *q, char *ch){

    if (isQueueFull(q))

        return;

    q->rear = (q->rear + 1) % q->cap;

    strcpy (q->array[q->rear], ch);

    q->size += 1;

}

char* deQueue(struct queue *q){

    if (isQueueEmpty(q))

        return NULL;

    q->front = (q->front + 1) % q->cap;

    q->size -= 1;

    return q->array[q->front];

    

}

void printQueue(struct queue *q){

    printf("Queue elements...\n");

    for (int i = 0; i < q->front; i++)

        printf("ele: %s\n", q->array[i]);

}

void toBinary(int n) {

    struct queue *q = createQueue(n);

    

    enQueue(q, "1");

    

    for (int i = 1; i <= n; i++) {

        char d1[10], d2[10];

        strcpy(d1, deQueue(q));

        printf("%s ", d1);

        strcpy(d2, d1);

        strcat(d1, "0");

        strcat(d2, "1");

        enQueue(q, d1);

        enQueue(q, d2);

    }

    printf("\n");

    free(q);

}

int main()

{

    // Note that size of arr[] is considered 100 according to

    // the constraints mentioned in problem statement.

    int arr[100], t, n;

 

    // Input the number of test cases you want to run

    scanf("%d", &t); 

 

    // One by one run for all input test cases

    while (t--)

    {

        // Input the size of the array

        scanf("%d", &n);

        toBinary(n);

    }

    return 0;

}