CNR - Editorial

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 .

SETTER’S SOLUTION

TESTER’S SOLUTION

2 Likes

There is an error while trying to download the setter’s or tester’s solution.Similar is the case for other editorials for lunchtime 5. How to download?

@h9k6 : I think the issue is now solved . Let us know if you still face any problem .

//