niklasb's blog

By niklasb, 6 years ago, ,

Earlier this day I came across a delightfully interesting question about an algorithm problem: http://stackoverflow.com/questions/23490944/recreate-the-sequence

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

So for every number in the sequence, Bob leaves over exactly one digit, and the position of that digit can vary between the numbers.

You are given the list of remaining digits and you should reconstruct the smallest starting value (in this case, 99) that could have resulted in the given sequence of digits.

OP claims there exists an algorithm. I suggested an algorithm for a starter, but I'm convinced we can do better. Any ideas?

• +24