Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in Java
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is a queue in data structure?
3.2.
Can the queue have NULL values?
3.3.
What is LinkedList?
4.
Conclusion
Last Updated: Mar 27, 2024

Generate Binary numbers from 1 to n using queue in Java

Author Harsh
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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

 

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a queue in data structure?

In programming, a queue is an important data structure. A queue operates on the FIFO (First In First Out) principle and is open at both ends. Data is inserted at one end of the queue, known as the back end or tail, and deleted at the other end, known as the front end or head of the queue.

 

Can the queue have NULL values?

In general, queue implementations do not allow the insertion of null members, although certain implementations, such as LinkedList, do allow.

 

What is LinkedList?

A linked list is a type of linear data structure in which the members are not stored in consecutive memory locations. Pointers are used to connect the elements of a linked list.

Conclusion

In this article, we have extensively discussed a coding problem in which we have to generate and print all the binary numbers that are ranging from 1 to n, and the value of n is given by the user.

We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more, check out our articles Binary Numbers of N digitsGenerate All Binary Numbers in the Range [L, R]C++ Program to Convert Binary Number to DecimalC++ Program to Convert Binary Number to OctalAdvantages of Circular Queue and many more on our Website.

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Previous article
Implementation of Queue using Arrays in C++
Next article
Introduction to Tree Data Structure
Live masterclass