An Interesting Method to generate Binary Numbers from 1 to n

Difficulty Level Medium
Frequently asked in Amazon Belzabar Mahindra Comviva ServiceNow Wooker
Breadth First Search QueueViews 2469

Problem Statement

The problem “An Interesting Method to generate Binary Numbers from 1 to n” states that you are given a number n, print all the numbers from 1 to n in binary form.

Examples

3
1 10 11

 

6

1 10 11 100 101 110

Algorithm

The generation of binary numbers from 1 to n can be seen as a binary tree, where 1 is the root of the tree and every node has 2 children, left child is obtained by appending ‘0’ at the end of the number while right child is obtained by appending ‘1’ at the end of the number. See the image below.

An Interesting Method to generate Binary Numbers from 1 to n

To generate first n binary numbers, do a level order traversal of the tree and print first n nodes.

  1. Create a queue of string named q. Initialize a variable total as 0.
  2. Push “1” to the queue, that is root of the tree.
  3. While the total is less than n, repeat step 4 and 5.
  4. Pop out an element from queue, print it and push its left child(element + “0”) and right child(element + “1”) to the queue.
  5. Increment total by 1.

Explanation

Consider the example that we have to generate binary number from 1 to 6.

First we create the tree as shown in image above, the root of the tree is 1, and for every node its left child is (value of node + “0”) and right child is (value of node + “1”).

In the tree we can see that the root corresponds to the binary representation of decimal number 1. The left child of root is the binary representation of 2, the right child of root is the binary representation of 3. Similarly, the left node of “2” is the binary representation of 4, and right node of “2” is the binary representation of 5 and so on.

So to print the binary representation of numbers from 1 to 6, all we have to do is to print the first 6 nodes of the tree, which can be done using a queue by traversing the tree in level order.

Hence, output is
1 10 11 100 101 110

Code

Java Code to An Interesting Method to generate Binary Numbers from 1 to n

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

class AnInterestingMethodToGenerateBinaryNumbersFrom1ToN {
    private static void generateBinaryNumbers(int n) {
        if (n == 0) {
            return;
        }

        // create a queue of strings
        Queue<String> q = new LinkedList<>();
        // push the root to the queue
        q.add("1");

        // initialize total as 0
        int total = 0;

        // while total is less than n
        while (total < n) {
            // remove an element from queue and print it
            String curr = q.poll();
            System.out.print(curr + " ");
            // add the left and right child of curr to the queue
            q.add(curr + "0");
            q.add(curr + "1");
            // increment total
            total++;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        int n1 = 3;
        generateBinaryNumbers(n1);

        int n2 = 6;
        generateBinaryNumbers(n2);
    }
}
1 10 11 
1 10 11 100 101 110

C++ Code to An Interesting Method to generate Binary Numbers from 1 to n

#include<bits/stdc++.h> 
using namespace std; 

void generateBinaryNumbers(int n) {
    if (n == 0) {
        return;
    }
    
    // create a queue of strings
    queue<string> q;
    // push the root to the queue
    q.push("1");
    
    // initialize total as 0
    int total = 0;
    
    // while total is less than n
    while (total < n) {
        // remove an element from queue and print it
        string curr = q.front();
        q.pop();
        cout<<curr<<" ";
        // add the left and right child of curr to the queue
        q.push(curr + "0");
        q.push(curr + "1");
        // increment total
        total++;
    }
    
    cout<<endl;
}

int main() {
    int n1 = 3;
    generateBinaryNumbers(n1);
    
    int n2 = 6;
    generateBinaryNumbers(n2);
    
    return 0;
}
1 10 11 
1 10 11 100 101 110

Complexity Analysis

Time Complexity

O(N), since we are only traversing the elements until we reach our given target element. Thus the algorithm is linear in time.

Space Complexity

O(N), as we have traversed through the elements which are less than the target element. We have been pushing these elements into the queue thus the space complexity is also linear.

Translate »