# 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 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 –

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

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 🙂

Get great deals at Amazon