Aspergillus's blog

Largest number from given digits and max continuous frequency k.
By Aspergillus, history, 3 hours ago, In English

I was asked this problem in an OA. I am given an n digit number (n <= 1e7), and a number k (<= n)

I was asked to build the largest possible number using some of these digits (maybe all), such that the largest continuous same digit length is <= k.

Thought a lot but could'nt solve. Now I am curious because the solution isnt available online.

pls help i beg.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

can you give a small example / test case plz . i mean how will the value of n and k be given? is it like n = 629 and k = 2 so the ans will 962 like this ?

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1112 k = 2 largest num is 1211

    → Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

First of all, using all digits provided is obviously optimal. To max the number, you should select the maximum possible digit starting from the most significant digit greedily. Now we try to simulate this process.

And now you would come up with this that looks juicy

This is actually not correct. At some point we might get stuck because there is only one type of digit left unused and we have already used $$$k$$$ of it.

So we have to check whether it's possible to complete the number using the rest digits every time we select a digit. Actually, this check can be done in $$$O(1)$$$ time with the following casework.

How to check if it's possible to complete the number with the rest digits

So we select digits from the highest bit to the lowest bit greedily. For each place, we select the largest digit that hasn't been continuously used for $$$k$$$ times and that it's possible to complete the number using the digits left.

→ Reply