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 2N -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
-
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.
-
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!