Generate Binary numbers from 1 to n using queue in Java

Introduction

A Queue is a First-In-First-Out (FIFO) data structure, which means that the first element added to the queue is the first one withdrawn. As a result, when a new element is added to the queue, all previous elements must be removed before the new element may be removed.

In this blog, we will discuss a popular problem and solve it using the queue Data Structure.

Problem Statement

Ninja has given you a number n, Your task is to print all the binary numbers ranging from 1 to n.

Sample Examples

Input

Output

Explanation

Approach

A simple approach would be to run a loop from 1 to n, and call the function decimal to binary inside the loop to convert all the numbers. We won’t be using this approach instead we will be using a queue data structure to solve the problem. The algorithm is explained below which will give us a clear idea about the approach.

Algorithm

1. Start
2. Create an empty queue.
3. Insert the first binary number(i.e. “1”) into the queue.
4. Get the front element from the queue and print it on the screen. Remove this element from the queue.
5. Add “0” at the end of the front element of the queue and insert it back into the queue.
6. Add “1” at the end of the front element of the queue and insert it into the queue.
7. Repeat steps 4, 5, and 6 “n ” times.
8. Exit

Implementation in Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class CodingNinja {
	
	// function to print binary numbers from 1 to n,
	static void genBinary(int n) {

		// creating an empty queue
		Queue<String> queue = new LinkedList<String>();

		// Enqueuing the first binary number into our queue
		queue.add("1");

		// loop to generate and print binary numbers from 1 to n;
		while (n-- > 0) {
			// printing the front element from the queue
			String c1 = queue.peek();
			queue.remove();
			System.out.println(c1);

			// Storing c1
			String c2 = c1;

			// Appending 0 to c1 and enqueuing it into our queue.
			queue.add(c1 + "0");

			// Appending 1 to c2 and enqueuing it into our queue.
			queue.add(c2 + "1");
		}
	}


	// main method
	public static void main(String[] args) {
		// getting the value of n from user
        System.out.print("Enter the value of n: ");
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

		// calling our function
		genBinary(n);
	}
}

You can also try this code with Online Java Compiler

Run Code

Input

Enter the value of n: 5

Output

1
10
11
100
101

Time Complexity

The time complexity of the above program is O(n) as we have to generate the binary numbers up to n.

Space Complexity

We are using a queue data structure in this approach. So, the space complexity of the above program is O(n).

Must read decimal to binary c++, Strong number in c

Read about Application of Queue in Data Structure here.