Generate binary numbers using a queue

May 11, 2019 Deb Haldar

Problem

Generate binary numbers from 1 to any given number, “n”, using a queue.

Function Signature

List<string> GenerateBinaryNumber(int n)

Example Input and Output

n = 1 => (1)

n = 3 => ( 1, 10, 11)

Problem Solving Strategy

Assuming you’ve never encountered this problem before and don’t have much experience using stacks and queues, try to discover a pattern. The first step of discovering a pattern is to write down a few sample inputs and outputs.

Decimal : 1 2 3 4 5

Binary : 1 10 11 1000 101

If you notice carefully, you’ll see that 2 is formed by appending a “0” to the previous number , “1”. And 3 is formed by appending a “1” to the previous previous number, 1. Similarly, 4 is formed by appending a “0” to 3 (“11”) and 5 is formed by appending a “1” to 3.

So could it be that if we keep on adding a “0” and “1” to the previously generated binary number, we can create this pattern ? Yes ! Let’s visualize how this will work with a Queue.

Visualize the Solution

We’ll use a queue to generate the numbers and a list(or array) to store the results.

So, after working through a graphic example, seems like this’ll work – so let’s formalize the algorithm

Algorithm

Create an empty Queue – this will be used to generate the binary numbers
Create an empty List/ Array – this will be used to hold the results , i.e, the list of generated binary numbers till n
Enqueue “1” in the queue
Generate the binary numbers inside a loop that runs till “n” binary numbers has been added to the list. Here’s what happens inside the loop:
- Remove an element from the queue – call this “X”
- Generate the next two binary numbers by adding a “0” and “1” to “X” respectively. The two new binary numbers thus generated are “X0” and “X1”
- Enqueue “X0” and “X1” into the queue
- Add “X” to the result list

Note: Once “n” elements have been added to the list, the loop terminates. At this point, there might be more elements left in the queue which will not be added to the results list ( since we only need n elements). But that is fine.

C# Implementation

using System;
using System.Collections.Generic;

namespace StacksNQueues
{
    public class GenerateBinaryNumbers
    {
        public static List<string> GenerateBinaryNumber(int n)
        {
            Queue<string> binaryGenerationQueue = new Queue<string>();
            List<string> results = new List<string>();

            binaryGenerationQueue.Enqueue("1");
            
            while(n!=0)
            {
                string current = binaryGenerationQueue.Dequeue();
                results.Add(current);

                string appendZero = current + "0";
                string appendOne = current + "1";

                binaryGenerationQueue.Enqueue(appendZero);
                binaryGenerationQueue.Enqueue(appendOne);

                n--;
            }
            return results;
        }
    }
}

And here’s the test program

using System;
using System.Collections.Generic;

namespace StacksNQueues
{
    class Program
    {
        static void Main(string[] args)
        {
            // test generate binary numbers using a queue
            List<string> testbinary0 = GenerateBinaryNumbers.GenerateBinaryNumber(0);
            List<string> testbinary1 = GenerateBinaryNumbers.GenerateBinaryNumber(1);
            List<string> testbinary3 = GenerateBinaryNumbers.GenerateBinaryNumber(3);
            List<string> testbinary5 = GenerateBinaryNumbers.GenerateBinaryNumber(5);
        }
    }
}