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..

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
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.