PROBLEM LINKS :
Practice
Contest
Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko
DIFFICULTY :
Easy
PREREQUISITES :
Permutations and Combinations , Binary Numbers , BigInteger Arithmetic
PROBLEM :
Given integers n , k and m , find the m’th lexicographically smallest binary string of length n with exactly k ones.
EXPLANATION:
Naive Solution 1 :
Generate all binary strings of length n with k ones. Sort them lexicographically and output the m’th elements.
Make a 2-D array of lists. list[i][j] : has the binary strings of length i with j ones . You can have i=0,j=0 and list containing empty string as base case and then fill rest of the entries iteratively . Sort list[n][k] and find the m entry in the list .
Naive Solution 2 :
Generate all binary strings of length n . Sort them lexicographically and then linearlly iterate to find the m’th element with k ones .
To generate all binary strings . Note that there will be 2^n such strings . So for i = 0 to i < 2^n for each integer convert the number i into its binary representation , the numbers will be already sorted so no need for sorting if you are generating this way . Just iterate and ouput the m’th element with k ones .
Full Solution :
If n-1 choose k is less than equal to m then first digit will be 0 .
If n-1 choose k is greater than m then first digit will be 1 .
Apply this recursively to get the answer string .
Note : The numbers involved in this problem will not fit in 32 or 64 bit integers . Use BigInteger library if using Java etc or write custom structures/functions to do BigInteger arithmetic .