Aspergillus's blog

Largest number from given digits and max continuous frequency k.
By Aspergillus, history, 6 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

»
6 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
  • »
    »
    6 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1112 k = 2 largest num is 1211

    → Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it +7 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
  • »
    »
    a moment ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the correct direction, I actually thought of something similar towards the end but couldn't properly formulate it in time. Now I have.

    Also, you mention that it is optimal to always use all the possible digits, but this is not always possible for example in cases with $$$s = 111112$$$ and $$$k = 2$$$, the highest number is obviously $$$11211$$$. Also you mention $$$a \leq kc - b$$$, while it should actually be $$$a \leq k(c + 1) - b$$$, since c digits can create $$$c + 1$$$ slots of width $$$k$$$

    I have tweaked the logic to take care of all of these little bits as well, below is an implementation of my final idea, so far no obvious WA.

    Code:
    → Reply