Find the missing number in a given string

Question

I found this interview question floating around, and after having given much thought to it, I couldn't really develop a sound algorithm for it.

Given a string of numbers in sequential order, find the missing number.The range of numbers is not given.

Sample Input:"9899100101103104105"

Answer:102

Answer 1

This is a simple problem.

1. Guess the number of digits for the first number
2. Read numbers from the string one by one. If the previous number you have read is x, the next number must be either x + 1 or x + 2. If it is x + 2, remember x + 1 as the missed number, continue until the end of the string anyway to verify that the initial guess was correct. If you read something else than x + 1 or x + 2, the initial guess was wrong and you need to restart with (next) guess.

With your example:

9899100101103104105

First guess length 1

read 9
the next number should be either 10 or 11. Read the next two digits, you get 89.
That is incorrect, so the initial guess was wrong.

Second guess length 2

read 98
the next number should be either 99 or 100. Read the next two digits for 99
the next number should be either 100 or 101. Read the next three digits for 100
... 101
... 103 (remember 102 as the missed number)
... 104
... 105
end of input

Guess of length 2 was verified as correct guess and 102 reported as missing number.