Given an infinite sequence of numbers:
12345678910111213141516..... and so on. I have to find a first position of an input string. Like this:
1234 gives 1 13 gives 16 111 gives 12
Anyone already figured out an algorithm for such question?
Hints:
If you know that the input string starts on a whole number, you can check that hypothesis quickly by trying all prefixes. For instance, take 21521.
2 can not be right as it continues as 2 3 4...
21 can not be right as it continues as 21 22 23...
215 is fine as it continues as 215 216...
It is also possible that the string does not start on a whole number, so you can try the suffixes as starting on a whole number, and check the preceding digits.
2 1521 can be 152 153..., but this is preceded by 15 1,
21 512 can be 512 513..., but this is preceded by 5 11,
215 12 can be 1 2 3..., but this is preceded by... nothing,
2151 2 can be 2 3..., but this is not preceded by enough digits.
Remains to find the index after you identified the match. You will have to accumulate the counts of the single digits numbers, the two digits numbers...
Also need to check that no possibility is missed.
At first sight, this process takes time O(N³) where N is the length of the string, whatever its position.