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.

Answer 2

The only dififcult part, of course, is figuring out how many digits the numbers have. I see two approaches.

1. Try a certain number of digits for the first number, decide what the following number should therefore be (there'll be two options, depending on whether the missing number is the second one), and see if that matches the following string of digits. If so, continue on. If the string doesn't fit the pattern, try again with a different number of digits.
2. Look at the starting and ending portions of the string, and reason the number of digits based on that and the length of the string. This one's a little more handwavey.

Answer 3

1. digits=1
2. parse the string like the first number conatins digits digits only.
3. parse the next number and check if it is sequential correct related to the last parsed one
4. if it decreases, digit+=1, goto 1.
5. if it is 2 higher than the last parsed, you might found the gap, parse the rest, if parsing the restis not an increasing sequence, digit+=1, goto 2, otherwise you have found the gap.
6. if it is 1 higher than the last parsed number, goto 3.
7. digit+=1, goto 2. (I am not sure if this case can ever happen)

Example:
given: "131416".
1. digits=1
2. parse '1' 3. parse '3'
4. it does not decrease
5. possibly found the gap: parse the rest '1416' fails, because '1' != '4'
=> digit+=1 (digit=2) goto 2
2. parse '13'
3. parse '14'
4. it does not decrease
5. it is no 2 higher than the last parsed one (13)
6. it is 1 higher (14 = 13+1) => goto 3
3. parse '16'
4. it does not decrease
5. possibly found the gap: parse the rest '' passed because nothing more to parse,
=> found the gab: '15' is the missing number

Answer 4

Here is a working C# solution you can check in LINQPad:

void Main()
{
    FindMissingNumberInString("9899100101103104105").Dump("Should be 102");
    FindMissingNumberInString("78910121314").Dump("Should be 11");
    FindMissingNumberInString("99899910011002").Dump("Should be 1000");

    // will throw InvalidOperationException, we're missing both 1000 and 1002
    FindMissingNumberInString("99899910011003");
}

public static int FindMissingNumberInString(string s)
{
    for (int digits = 1; digits < 4; digits++)
    {
        int[] numbers = GetNumbersFromString(s, digits);
        int result;
        if (FindMissingNumber(numbers, out result))
            return result;
    }
    throw new InvalidOperationException("Unable to determine the missing number fro '" + s + "'");
}

public static int[] GetNumbersFromString(string s, int digits)
{
    var result = new List<int>();
    int index = digits;
    int number = int.Parse(s.Substring(0, digits));
    result.Add(number);

    while (index < s.Length)
    {
        string part;
        number++;
        digits = number.ToString().Length;
        if (s.Length - index < digits)
            part = s.Substring(index);
        else
            part = s.Substring(index, digits);
        result.Add(int.Parse(part));
        index += digits;
    }
    return result.ToArray();
}

public static bool FindMissingNumber(int[] numbers, out int missingNumber)
{
    missingNumber = 0;

    int? found = null;
    for (int index = 1; index < numbers.Length; index++)
    {
        switch (numbers[index] - numbers[index - 1])
        {
            case 1:
                // sequence continuing OK
                break;

            case 2:
                // gap we expect to occur once
                if (found == null)
                    found = numbers[index] - 1;
                else
                {
                    // occured twice
                    return false;
                }
                break;

            default:
                // not the right sequence
                return false;
        }
    }

    if (found.HasValue)
    {
        missingNumber = found.Value;
        return true;
    }

    return false;
}

This can likely be vastly simplified but during exploratory coding I like to write out clear and easy to understand code rather than trying to write it in as few lines of code or as fast as possible.