Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Cpp Code
3.2.
Java Code
3.3.
Python Code
3.4.
Output
3.5.
Complexity Analysis
3.5.1.
Time Complexity: O(2N )
3.5.2.
Space Complexity: O(N)
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Binary Numbers of N digits

Author Rhythm Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Today, we have a problem where we need to print all the binary numbers of N digits.

Without any further delays, let's move to our problem statement.

Problem Statement

We have an integer N. Our task is to generate all the binary numbers of N digits in ascending order.

Example:

Assume we have the following integer as input:

Input:

3

Output:

000

001

010

011

100

101

110

111

Explanation:

These are all the three digits numbers in their binary form in ascending order.

Approach

We can approach this problem in a Naive manner. We know that for N digits, total possible combinations of digits yield a total of 2N numbers. So we simply iterate over a for-loop from 0 to 2N and print the binary representation of each number.
 

Algorithm:

  • Create a function “bin” that prints the binary representation of a number (32 bit long).
    • Use an array to store the binary representation of the number.
    • Use a for loop that iterates from 0 to N-1 (since we have a total of N digits) and extracts each bit one by one by right shifting the number.
       
  • Now for a function that generates all the binary numbers, Create a for-loop that iterates from 0 to 2-1.
  • For each number, call bin.

Cpp Code

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


//function that prints binary representation
void bin(int digit,int n){
    vector<int> arr;
    for(int i=0;i<digit;i++){
        arr.push_back(n%2);
        n=n>>1;
    }
    for(int i=digit-1;i>=0;i--){
        cout<<arr[i];
    }
}
//function to generate all binary numbers of N digit.
void generateAllBin(int n){
    int high=pow(2, n);
    for(int i=0;i<high;i++){
        bin(n,i);
        cout<<endl;
    }
}
int main()
{
    generateAllBin(3);
    return 0;
}

Java Code

import java.util.*;
public class Main
{
   //function that prints binary representation
   public static void bin(int digit,int n){
       List arr = new ArrayList<Integer>();
       for(int i=0;i<digit;i++){
           arr.add(n%2);
           n=n>>1;
       }
       for(int i=digit-1;i>=0;i--){
           System.out.print(arr.get(i));
       }
   }
   //function to generate all binary numbers of N digit.
   public static void generateAllBin(int n){
       int high=(int)Math.pow(2, n);
       for(int i=0;i<high;i++){
           bin(n,i);
           System.out.println();
       }
   }
public static void main(String[] args) {
    generateAllBin(3);
}
}
You can also try this code with Online Java Compiler
Run Code

Python Code

# function that prints binary representation
def bin(digit, n):
   arr = []
   for i in range(digit):
       arr.append(n%2)
       n = n>>1
       
   for i in range(digit-1, -1, -1):
       print(arr[i],end="")
       
# function to generate all binary numbers of N digit.      
def generateAllBin(n):
   high = int(pow(2, n))
   for i in range(high):
       bin(n, i)
       print()
       
       
generateAllBin(3)
You can also try this code with Online Python Compiler
Run Code

Output

000

001

010

011

100

101

110

111

Complexity Analysis

Time Complexity: O(2N )

Since the total possible number of N digits is 2N, we did a constant amount of work for each number.

Space Complexity: O(N)

We have to use an array of size N to store the binary representation of a binary number having N digits.

Must read decimal to binary c++, and Euclid GCD Algorithm

Frequently Asked Questions

  1. Why is a constant amount of work required for conversion to binary?
    Usually, integers are represented as 32 bits. So for conversion of integer from base 10 to base 2, we would require approx 32 calculations at maximum. Therefore, a constant amount of work involved O(32) converting from decimal to binary.
     
  2. How do we check if the current bit is 1 or 0?
    For a given bit, we can do a bitwise AND with 1. If bitwise AND of the given bit with 1 yields 1, then the bit was 1; else, it was 0.

Key Takeaways

Today we encountered a fundamental question based on bitwise calculations involved. This kind of problem cannot be solved using any other approach and require knowledge of bitwise operators.
To learn about bitwise operators in C and C++, you can have a look at Bitwise Operators in C/C++.

Happy Coding!

Live masterclass