Given a number N, write a function that generates and prints all binary numbers with decimal values from 1 to N.
Examples:
Input: n = 2
Output: 1, 10Input: n = 5
Output: 1, 10, 11, 100, 101
Naive Method: To solve the problem follow the below idea:
A simple method is to run a loop from 1 to n, and call decimal to binary inside the loop.
Code-
C++
// C++ program to generate binary numbers from 1 to n#include <bits/stdc++.h>using namespace std;void generatePrintBinary(int n){ for(int i=1;i<=n;i++){ string str=""; int temp=i; while(temp){ if(temp&1){str=to_string(1)+str;} else{str=to_string(0)+str;} temp=temp>>1; } cout<<str<<endl; }}// Driver codeint main(){ int n = 10; // Function call generatePrintBinary(n); return 0;} |
Java
// Java program to generate binary numbers from 1 to nimport java.util.*;public class Main { static void generatePrintBinary(int n) { for (int i = 1; i <= n; i++) { String str = ""; int temp = i; while (temp != 0) { if ((temp & 1) == 1) { str = "1" + str; } else { str = "0" + str; } temp = temp >> 1; } System.out.println(str); } } // Driver code public static void main(String[] args) { int n = 10; // Function call generatePrintBinary(n); }} |
Python3
# Function to generate binary numbers from 1 to ndef generatePrintBinary(n): for i in range(1, n + 1): str = "" temp = i # Convert decimal number to binary number while temp: if temp & 1: str = "1" + str else: str = "0" + str temp >>= 1 # Right shift the bits of temp by 1 position print(str)n = 10# Function callgeneratePrintBinary(n) |
C#
// C# program to generate binary numbers from 1 to nusing System;class GFG { static void generatePrintBinary(int n) { for (int i = 1; i <= n; i++) { string str = ""; int temp = i; while (temp != 0) { if ((temp & 1) != 0) { str = "1" + str; } else { str = "0" + str; } temp = temp >> 1; } Console.WriteLine(str); } } // Driver code static void Main() { int n = 10; // Function call generatePrintBinary(n); }} |
Javascript
// JavaScript program to generate binary numbers from 1 to nfunction generatePrintBinary(n) { for (let i = 1; i <= n; i++) { let str = ""; let temp = i; while (temp) { if (temp & 1) { str = "1" + str; } else { str = "0" + str; } temp = temp >> 1; } console.log(str); }}// Driver codelet n = 10;// Function callgeneratePrintBinary(n); |
Output-
1 10 11 100 101 110 111 1000 1001 1010
Time Complexity: O(N*logN),N for traversing from 1 to N and logN for decimal to binary conversion
Auxiliary Space: O(1)
Generate Binary Numbers from 1 to n using the queue:
Follow the given steps to solve the problem:
- Create an empty queue of strings
- Enqueue the first binary number “1” to the queue.
- Now run a loop for generating and printing n binary numbers.
- Dequeue and Print the front of queue.
- Append “0” at the end of front item and enqueue it.
- Append “1” at the end of front item and enqueue it.
Thanks to Vivek for suggesting this approach.
Below is the implementation of the above approach:
C++
// C++ program to generate binary numbers from 1 to n#include <bits/stdc++.h>using namespace std;// This function uses queue data structure to print binary// numbersvoid generatePrintBinary(int n){ // Create an empty queue of strings queue<string> q; // Enqueue the first binary number q.push("1"); // This loops is like BFS of a tree with 1 as root // 0 as left child and 1 as right child and so on while (n--) { // print the front of queue string s1 = q.front(); q.pop(); cout << s1 << "\n"; string s2 = s1; // Store s1 before changing it // Append "0" to s1 and enqueue it q.push(s1.append("0")); // Append "1" to s2 and enqueue it. Note that s2 // contains the previous front q.push(s2.append("1")); }}// Driver codeint main(){ int n = 10; // Function call generatePrintBinary(n); return 0;} |
Java
// Java program to generate binary numbers from 1 to nimport java.util.LinkedList;import java.util.Queue;public class GenerateBNo { // This function uses queue data structure to print // binary numbers static void generatePrintBinary(int n) { // Create an empty queue of strings Queue<String> q = new LinkedList<String>(); // Enqueue the first binary number q.add("1"); // This loops is like BFS of a tree with 1 as root // 0 as left child and 1 as right child and so on while (n-- > 0) { // print the front of queue String s1 = q.peek(); q.remove(); System.out.println(s1); // Store s1 before changing it String s2 = s1; // Append "0" to s1 and enqueue it q.add(s1 + "0"); // Append "1" to s2 and enqueue it. Note that s2 // contains the previous front q.add(s2 + "1"); } } // Driver code public static void main(String[] args) { int n = 10; // Function call generatePrintBinary(n); }}// This code is contributed by Sumit Ghosh |
Python3
# Python3 program to generate binary numbers from# 1 to n# This function uses queue data structure to print binary numbersdef generatePrintBinary(n): # Create an empty queue from queue import Queue q = Queue() # Enqueue the first binary number q.put("1") # This loop is like BFS of a tree with 1 as root # 0 as left child and 1 as right child and so on while(n > 0): n -= 1 # Print the front of queue s1 = q.get() print(s1) s2 = s1 # Store s1 before changing it # Append "0" to s1 and enqueue it q.put(s1+"0") # Append "1" to s2 and enqueue it. Note that s2 # contains the previous front q.put(s2+"1")# Driver codeif __name__ == "__main__": n = 10 # Function call generatePrintBinary(n)# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to generate binary// numbers from 1 to nusing System;using System.Collections.Generic;class GFG { // This function uses queue data // structure to print binary numbers public static void generatePrintBinary(int n) { // Create an empty queue of strings LinkedList<string> q = new LinkedList<string>(); // Enqueue the first binary number q.AddLast("1"); // This loops is like BFS of a tree // with 1 as root 0 as left child // and 1 as right child and so on while (n-- > 0) { // print the front of queue string s1 = q.First.Value; q.RemoveFirst(); Console.WriteLine(s1); // Store s1 before changing it string s2 = s1; // Append "0" to s1 and enqueue it q.AddLast(s1 + "0"); // Append "1" to s2 and enqueue it. // Note that s2 contains the previous front q.AddLast(s2 + "1"); } } // Driver Code public static void Main(string[] args) { int n = 10; // Function call generatePrintBinary(n); }}// This code is contributed by Shrikant13 |
Javascript
<script>// JavaScript program to generate binary numbers from 1 to n// This function uses queue data structure to print binary// numbersfunction generatePrintBinary(n){ // Create an empty queue of strings var q = []; // Enqueue the first binary number q.push("1"); // This loops is like BFS of a tree with 1 as root // 0 as left child and 1 as right child and so on while (n--) { // print the front of queue var s1 = q[0]; q.shift(); document.write( s1 + "<br>"); var s2 = s1; // Store s1 before changing it // Append "0" to s1 and enqueue it q.push(s1+"0"); // Append "1" to s2 and enqueue it. Note that s2 // contains the previous front q.push(s2+"1"); }}// Driver program to test above functionvar n = 10;generatePrintBinary(n);</script> |
Output
1 10 11 100 101 110 111 1000 1001 1010
Time Complexity: O(N)
Auxiliary Space: O(N) as extra space is required in this method
This article is contributed by Abhishek. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
