Generate binary numbers between 1 to N

Given a positive number N, efficiently generate all binary numbers between 1 to N.

 

For example, for N = 10, the binary numbers are


1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

 


 

Approach 1: Using Queue –

 
C++ implementation –
 

Download   Run Code

Output:

1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

Approach 2: Using std::bitset

 
C++ implementation –
 

Download   Run Code

Output:

00000001 00000010 00000011 00000100 00000101 00000110 00000111 00001000
00001001 00001010 00001011 00001100 00001101 00001110 00001111 00010000

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂