An Interesting Method to Generate Binary Numbers from 1 to n

Last Updated : 05 Apr, 2023

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, 10

Input: 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 code
int main()
{
    int n = 10;
 
    // Function call
    generatePrintBinary(n);
    return 0;
}

Java

// Java program to generate binary numbers from 1 to n
import 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 n
def 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 call
generatePrintBinary(n)

C#

// C# program to generate binary numbers from 1 to n
using 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 n
 
function 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 code
let n = 10;
 
// Function call
generatePrintBinary(n);

Output-

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
// numbers
void 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 code
int main()
{
    int n = 10;
 
    // Function call
    generatePrintBinary(n);
    return 0;
}

Java

// Java program to generate binary numbers from 1 to n
 
import 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 numbers
 
 
def 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 code
if __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 n
using 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
// numbers
function 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 function
var n = 10;
generatePrintBinary(n);
 
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N) as extra space is required in this method

Suggest improvement

Minimum time required to rotten all oranges

Maximum cost path from source node to destination node via at most K intermediate nodes

Share your thoughts in the comments

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue

An Interesting Method to Generate Binary Numbers from 1 to n

C++

Java

Python3

C#

Javascript

Generate Binary Numbers from 1 to n using the queue:

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?