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