algorithm - Recreate the Sequence -

I've come to the following problem, which has since been in my mind:

Alice wrote Is continuous, positive, integers on a blackboard such as N such as "99, 100, 101, 102" . Bob has erased all the digits, but one, from each number, so that the sequence now reads eg. "9, 0, 0, 1" . Note that the digit which he leaves can be different for every integer.

Our task, O (n log n ), in the complexity of time, the sequence may start to find the smallest number, the answer in the above example would be 99 < For the / code> length 7 sequence "1, 4, 0, 5, 4, 1, 4" , the answer would be 1042 . (Which generates the sequence of 1042, 1043, 1044, 1045, 1046, 1047, 1048,.) ​​

I can show the upper limit to almost 1234567890 * N , so output Can not be of an unlimited size, though I am not able to even get an efficient o (n ^ 2) solution.

Any thoughts?

Update: For those interested, this problem (this is " Sequence "). , Here's an O (n log n) solution: Try every possible final digit of the starting value, in the groups of grouped array elements, which are 0 to 9 digits in the end (this can be estimated from the last digit of the initial value ). We know that all the values ​​of the same group have the same prefix, when we remove our last digit, let's eliminate all those values ​​where the digit of the input matches the last digit should according to his position.

Now we have a little subproblem: 10 for each group, we know of a set of the digits appearing in our prefix. We fall into an array element. This normalized problem is only a tenth of the size of the original problem and can be solved using the same algorithm.

We recapitulate T (n) = 10 * t (n / 10) + o (n), which we use when using the master theorem (n) = he (n log n) Resolve in the form.

Example:

We say input [1, 4, 0, 5, 4, 1, 4, 9, 5, 0 , 1, 0] . So in generalized form, we know the following subsets of the digits for each position:

  {1} {4} {0} {5} {4} {1} {4} {9} {5} {0} {1} {0}  

We check the number 2 as the last digit of the initial number (i.e. We examine all of us are also second digits, but this branch will be closed to include the minimum solution). We know that the order of the last digits

  2 3 4 5 6 7 8 9 0 1 2 3  

So we know the groups with whom Is the same prefix (2- 9 and 0-3). We also eliminate those points of the digits that we already know in the right position:

  {1} {4} {0} {} {4} {1} {4} {} | {5} {0} {1} {0}  

By collecting all the points of each group, we reach less problem

  {0 , 1,4} {0,1,5}  

Then we press the second revolutionary force from the second number. Suppose we are checking 4 we get it:

  4 5 {0} {0,1}  < / Pre> 
 which reduces 
 
  {0,1}  
 
 Now that we are only under an array element, we Those numbers will need to create the smallest number of lexicography which is not a major zero, which is  10 . Hence the result is  1042 . 
 
 Older version 
 
 I believe there is a major overview here that in this kind of progress, the length of N, only the last limit (log_10 (n)) is one Change more often than Therefore we can kill the number before the last limit (log_10 (n)), at the end of the prefix, nine digits and o (n * log n). 
 
 Then we fix the pattern 
 
  P..PX9..9S ... s  
 
 where suffix is ​​known , The number of nines is known, X & LT; 9 is known, but the prefix is ​​not p. 
 
 Now we can remove that number from those sequences which already match one of the scores we already know, appear in their respective place. We are left with a set of points, which we know is the prefix p. We just create a small string of lexicography in which there are no leading zeros and all the digits are included. 
 
 Runtime O (n ^ 2 log n).