Substring in a infinite sequence of numbers

Question

I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers.

Example:

1234567891011121314151617181920 ...

S = 141

Result: 18

All i think about is convert sequence to string and find substring using Rabin-Karp or KMP. But i feel that i can use it as numbers and there is some O(1) solution using math.

Another thought is split S on pieces:

141 = [(1, 4, 1), (1, 41), (14, 1), (141)]

And i have (1-9)(10-99)(100-999)(1000-9999)... which represents infinite sequence.

Than i can use this algo:

For (1, 41): try to find 1 from (1-9) and what goes next, if 41 is not next number, than try next tuple.

For (14, 1): try to find 14 from (10-99) and and what goes next, if 1 than find position of '14'.

But i'm not sure that this is correct solution. Maybe some advices?

Answer 1

Your algorithm is not correct. Consider 21:

21 = [(2, 1), (21)]

First we find 2 in (1-9): 123456789. However, a 3 follows, so it's not a solution.

Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution:

123456789101112131415161718192021

So the solution is not correct.

The sequence you're after is A229186, but no simple formula is posted there.

Answer 2

I don't think an $\mathcal{O}(1)$ solution can be possible, since if nothing else, you need to examine all digits of your input. But if n is the number of digits in your input (such that the numerical value of your input is between $10^{n-1}$ and $10^n$), there's definitely a polynomial-time solution in n, whereas the substring–based approaches (that don't take into account the structure of the sequence) are necessarily $\Omega\left(10^n\right)$.

One approach:

• First, test the possibility that the last digit of your input corresponds to a single-digit number in the infinite sequence. (For example, $234$ passes this test: the $4$ is the sequence's $4$.) If so, you're done.

• Next, test the possibilities that the last digit of your input corresponds to:

  • the first digit of a two-digit number in the infinite sequence. (For example, $121$ passes this test: the second $1$ is the first digit of the sequence's $13$.)
  • the second (last) digit of a two-digit number in the infinite sequence. (For example, $112$ passes this test: the $12$ is the sequence's $12$.)

  If either of these checks out, then you're done. (If both check out, then choose the one that gives you an earlier index.)

• Next, test the possibilities that the last digit of your input corresponds to the first, the second, or the third digit of a three-digit number in the infinite sequence.

• . . . and so on until you have a result. (It's guaranteed that you'll have results once you get to the possibilities where the last digit of the input corresponds to a digit of an n-digit number in the infinite sequence; so your algorithm will terminate there, if not before.)

Overall, you have to test at most $\Theta\left(n^2\right)$ possibilities. I haven't described exactly how you actually perform each test, but you should be able to do so in $\Theta\left(n\right)$ time, and you should be able to compare two successful possibilities in $\Theta\left(1\right)$ time to decide which one comes earlier in the sequence. You'll also need to translate the final result from something like "ends on the second digit of the sequence's $234$" to something like "starts at position 587"; but you can certainly do that in $\mathcal{O}\left(n^2\right)$ time (and probably $\Theta\left(n\right)$ time), so your total complexity should be worst-case $\Theta\left(n^2\right)$.

Answer 3

This would be an excellent place for a state machine. Create a state machine with states from S. You should have a state for "I haven't matched anything", one for "I've matched the first character," one for "I've matched the first two characters" and so on. In your example, we would have 4 states { "", "1", "14", "141" }. The final state is terminating. If you mach the whole string (141), then you have found your first match in the infinite string.

Now you can build your state transition diagram. The key to building this is that you can fail to match the next character, but not have to start over at the beginning. 141 is a bad example, but consider 444441. If I were to be matching "132444444..." I clearly start matching 444441 at the obvious point, but when I see a "4" when I wanted to see a "1", I shouldn't start over. I've still got a match of several 4's in a row. Maybe the next character will be a 1!

We can write up a transition diagram. In this case, I'll notate it with the current state on the left, a colon, and then a set of transitions on the right side of the colon. The inputs will be unquoted digits, and the new states will be quoted strings. In your simple example, 141, the transition diagram is:

"":   1 -> "1"           other -> ""
"1":  4 -> "14"  1-> "1" other -> ""
"14": 1 -> "141"         other -> ""
"141" terminates

This clearly can process each additional character of the string in O(1) time.

In a more complicated example, such as S = "5451" we need to take into account the possibility of a partial match. Otherwise, the process is the same

"":    5 -> "5"                     other -> ""
"5":   4 -> "54"  5-> "5"           other -> ""
"54":  5 -> "545"                   other -> ""
"545": 1 -> "5451" 4-> "54" 5-> "5" other -> ""
"5451" terminates

Note that on "545", there are many possible transitions which capture the fact that there were partial matches.

If you are interested in prior art KMP is a good algorithm to explore. There are also more exotic sub-linear ones which can actually skip characters entirely (as long as there's a way to go back and visit those characters if a potential match shows up).

Answer 4

Consider the number you want to search

eg 141 , see the digit in number lesser than or equal to the first digit

[ Intuition: If less maybe , we can bring it to the front, If equal maybe the rest is the next number in the series]

Following this:

See 141 , 1 in the third place is equal to the first digit.

So here we go position of 14 (with a check that 15 comes after 14, Maybe its like (191, where 19+1 = 20 in which case we are wrong )

Another example

21 , 1 is lesser than 2 , so 12 13 and we are done.

Another one 1254

Since no number is greater than or equal to 1 , answer is 1254

Another one 5421

1 is the least so 1542 1543

Another one 191

1 is least so, 19+1 = 20 (No!!) So answer is 191.

1911

Here we see we can solve by , 19 11 , take to front 11 19 11 20.

Or let the last one stay (tie as 1), so 191 192. So the answer is 191

In this case your algorithm will be max O(size of pattern) , instead of O(size of text) as in kmp, assuming you can calculate index in O(1) by a formula.

Code this up and you are done :)