Find missing number in sequence in string [closed]

Question

I have a string that contains numbers in sequence. There are no delimiters between numbers. I have to find missing number in that sequence. For example:

176517661768 is missing the number: 1767
8632456863245786324598632460 is missing the number: 8632458

I have no idea how to even start. As you can see, I don't know the number length either. On top of that, I am mostly a C programmer so get little help from inbuilt functions. Nevertheless I am looking for a good algorithm that I can implement myself. However, code/pseudo-code is highly appreciated.

Answer 1

The problem is entirely one of forming a hypothesis and testing it.

So, we have 176517661768. Ok. The first hypothesis is that the first number is one digit long. That would be a 1. This would mean that I expect the next number to be either a 2 or 3 (if the hole is a 2). Lets check that out.

• 1 - got it.
• 7 - not a 2 or a 3.

Ok, lets throw that out.

The second hypothesis is that the first number is two digits long. That would be a 17. This would mean that I expect the number to be 18 or 19.

• 17 - got it
• 65 - not 18 or 19.

Lets try this again. It might be three digits long. That would mean 176.

• 176 - got it
• 517 - not a 177 or 178.

Lets try this yet again. It might be four digits long.

• 1765 - got it
• 1766 - still matching with the hypothesis
• 1768 - still matching with the hypothesis (and we have a hole, set that aside)..
• ...

Figuring out how to do the appropriate substrings or stream processing is left as an exercise to the reader for their chosen language. This will likely fall into the approach where you are writing a type of state machine where you are only going forward and testing for two possible conditions - the next value or the next value plus one (and once you find a situation where you've accepted next value plus one, all future states have only one acceptance test - that of next value).