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.

  • recommended reading: Where to start? – gnat Feb 16 '16 at 16:39
  • Is it possible for the sequence to change the number of digits over the course of the string? 99101 or 98100 being examples of this. – user40980 Feb 16 '16 at 16:43
  • Woah! So many downvotes! Somebody care to point out what's wrong with the question? I am new. – Neo Feb 16 '16 at 17:15
  • 1
    @Neo the combination of not trying anything initially and asking for code or pseudocode. Yes, you don't know where to start but thinking through a problem is a key part to figuring out how to solve it. What if you were given this as a string of tiles with numbers written on them - how do you (as a person) identify the sequence? – user40980 Feb 16 '16 at 17:58
  • Autocorrelation of the sequence, will reveal the cycle length of the substring. And then you will know that the first string has a cycle length of 4 and for the second string has 7. You might find out the next steps to do then. – thepacker Feb 16 '16 at 18:13

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.