Printing 1 to N in Binary Using Queue

One of the popular interview question asked on queue data structure:

Write a program to print the numbers from 1 to N in Binary Representation using QUEUE data structure.

Example:
Input: N = 3
Output: 1, 10, 11

Input: N= 5
Output: 1, 10, 11, 100, 101

Code will follow the following Logic:

• Initialize queue with 1
• Repeat this step until required ‘n’ is reached
  • Dequeue front and print
  • Suffix front element with ‘0’ once and ‘1’ another and enqueue both into queue in the same order

One possible C Implementation Solution:

#include <stdio.h>
#include <string.h>

struct queue
{
    char items[50][20];
    int front;
    int rear;
};
typedef struct queue QUEUE;

void enqueue(QUEUE *q, char x[])
{
    q->rear++;
    strcpy(q->items[q->rear], x);
}

void dequeue(QUEUE *q, char *x)
{
    strcpy(x, q->items[q->front]);
    q->front++;
}

void print_binary(int n)
{
    QUEUE q;
    q.front = 0;
    q.rear = -1;
    char x[20], tx[20];
    int i = 1;

    enqueue(&q, "1");

    while(i <= n)
    {
        dequeue(&q, x);

        // Copy the value to temp so that we dont lose it
        // for second time append
        strcpy(tx, x);

        // Print the dequeued item
        printf("%s\t", x);

        // Append a 0 and enqueue
        enqueue(&q, (strcat(x, "0")));

        // Copy back the original string
        strcpy(x, tx);

        // Append a 1 and enqueue
        enqueue(&q, (strcat(x, "1")));

        i++;
    }
}

int main()
{
    int n;
    printf("Enter the value of n");
    scanf("%d", &n);

    print_binary(n);

    return 0;
}

Advertisements