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

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 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 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(N2).

 

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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz