# Generate binary numbers using a queue

## 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); } } }

## Complexity Analysis

**Runtime complexity :** O(n) since we only loop till we’ve generated n numbers and the runtime increases lineraly as n becomes bigger

**Space complexity:** O(2n) = O(n) because we use a queue and a List/Array for processing and holding the results