Find all N-digit binary numbers with k-bits set where k ranges from 1 to N

Write a program to print all N-digit binary numbers with k-bits set where k ranges from 1 to N. Numbers with same number of bits set should be printed together and in ascending order.

 

For example,


4-digit binary numbers are –

(k = 1) 0001 0010 0100 1000
(k = 2) 0011 0101 0110 1001 1010 1100
(k = 3) 0111 1011 1101 1110
(k = 4) 1111
 

5-digit binary numbers are –

(k = 1) 00001 00010 00100 01000 10000
(k = 2) 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000
(k = 3) 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100
(k = 4) 01111 10111 11011 11101 11110
(k = 5) 11111

 

 
The idea is to use std::next_permutation that generates the next greater lexicographic permutation of a string. To print all numbers with k-bit set in ascending order, we set last k bits of a N-digit number to 1 and then use std::next_permutation to print numbers in lexicographical order.

 
C++ implementation –
 

Download   Run Code

Output:

(k = 1) 0001 0010 0100 1000
(k = 2) 0011 0101 0110 1001 1010 1100
(k = 3) 0111 1011 1101 1110
(k = 4) 1111

 
The time complexity of above solution is O(N2) and auxiliary space used by the program is O(N) where N is the number of digits..

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
yndi
Guest

I believe the time complexity is O(2^n), and the space complexity is O(n) here.