Recreate the Sequence

Question

I came across the following problem, which has been on my mind ever since:

Alice has written N consecutive, positive integers on a blackboard. E.g. "99, 100, 101, 102". Bob has erased all digits, but one, from each number, so the sequence now reads e.g. "9, 0, 0, 1". Notice that the digit he leaves over can be a different one for every integer.

Our task is, in O(N log N) time complexity, to find the smallest number that may have started the sequence. In the above example the answer would be 99. For the length 7 sequence "1, 4, 0, 5, 4, 1, 4" , the answer would be 1042. (Which yield the sequence 1042, 1043, 1044, 1045, 1046, 1047, 1048).

I can show an upper bound up of around 1234567890*N, so the output can't be of unlimited size. However I haven't been able to even find an efficient O(N^2) solution.

Any ideas?

Answer 1

UPDATE: For those interested, this problem appeared in the Baltic Olympiad in Informatics (BOI) 2014 (it's the task "Sequence"). Due to Codeforces user Fdg, here's an O(N log N) solution: Try every possible last digit of the starting value. Partition contiguous array elements into groups that have the digits 0 to 9 at the end (this can be inferred from the starting value's last digit). We know that all values in the same group have the same prefix, after we remove their last digit. Let's eliminate all those values where the digit in the input matches the last digit that it should have according to their position.

Now we have a slightly different subproblem: For every group of 10, we know a set of digits that appear in its prefix. We collapse this into a single array element. This generalized problem only has one tenth the size of the original problem and can be solved using the same algorithm, recursively.

We thus get the recurrence T(N) = 10 * T(N / 10) + O(N), which we solve as T(N) = O(N log N) using the master theorem.

Example:

Let's say the input is [1, 4, 0, 5, 4, 1, 4, 9, 5, 0, 1, 0]. So in the generalized form, we know the following subsets of digits for every position:

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

We check the number 2 as the last digit of the starting number (of course we check all the other digits too, but this branch will turn out to contain the minimum solution). We know that the sequence of last digits goes like

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

So we know the groups that have the same prefix (2-9 and 0-3). We also eliminate those digits from the sets that we already know are at the correct position:

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

By collecting all the digits of each group, we arrive at the reduced problem

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

Again we brute-force the second to last digit. Let's say we are checking 4. We get:

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

Which reduces to

{0,1}

Now that we are down to only one array element, we just have to build the lexicographically smallest number out of those digits that has no leading zeroes, which is 10. So the result is 1042.

Old version

I believe one key observation here is that in a progression like this, of length N, only the last ceil(log_10(N)) digits are changed more than once. So we could brute-force the last ceil(log_10(N)) digits, the number of nines at the end of the prefix and the digit before that in O(N * log N).

So we fix the pattern

P..PX9..9S...S

where the suffix S is known, the number of nines is known, X < 9 is known, but the prefix P is not.

We can now remove those numbers from the sequence that already match one of the digits we already know appears at their respective position. We are left with a set of digits which we know comprise the prefix P. We just form the lexicographically smallest string that has no leading zeroes and contains all the digits.

The runtime is O(N^2 log N).