How to find a missing number from a string of digits without spaces between them?

Question

Input Format

The first line will contain the set of numbers in the sequence. Number are listed in ascending order.

Boundary Conditions

1<=M<=99999 Length of string S is from 5 to 200.

Output Format

The first line will contain the missing number M.

Example Input /Output 1

Input: 12346789

Output: 5

Input /Output 2 Input 596597598600601602

Output : 599

The numbers a sequence in the sequence are 596 597 598 599 600 601 602. 599 is the missing numbers

My Java solution is:

I have used split(("?<=\\G...")), etc., to split the numbers into one, two, three four and five digits. And saved the numbers into a corresponding array. Then I checked for any difference between two adjacent numbers in a array - if it is one then it will invoke a function to find the missing number.

But problem is that when:

Input:

999899991000110002 

Output :

10000

the sequence is 9998 9999 10001 10002. The missing number is 10000

How would I split the string when a transition from a 4 digit to a 5 digit number is possible? Is there any better way of solving this problem?

public void test(Scanner in)
{
    String n = in.nextLine();
    int n1 = n.length();
    System.out.println(n1);
    if (n1 % 2 == 0)
    {

    } else {
      n = "0" + n;
    }
    System.out.println(n);
    String[] one = n.split("(?<=\\G.)");
    String[] two = n.split("(?<=\\G..)");
    String[] three = n.split("(?<=\\G...)");
    String[] four = n.split("(?<=\\G....)");
    String[] five = n.split("(?<=\\G.....)");
    int x = one.length;
    int y = two.length;
    int z = three.length;
    int u = four.length;
    int v = five.length;
    int[] aa1 = new int [x];
    int[] aa2 = new int [y];
    int[] aa3 = new int [z];
    int[] aa4 = new int [u];
    int[] aa5 = new int [v];
    for (int i = 0; i < x; i++)
    {
        aa1[i] = Integer.parseInt(one[i]);
    }
    if (aa1[1] == aa1[3] - 2)
    {
        findmissing(aa1, x);          
    }
    for (int i = 0; i < y; i++)
    {
        aa2[i] = Integer.parseInt(two[i]);
    }
    if (aa2[1] == aa2[3] - 2)
    {
        findmissing(aa2, y);
    }
    for (int i = 0; i < z; i++)
    {
        aa3[i] = Integer.parseInt(three[i]);
    }
    if (aa3[1] == aa3[3] - 2)
    {
        findmissing(aa3, z);
    }
    for (int i = 0; i < u; i++)
    {
        aa4[i] = Integer.parseInt(four[i]);
    }
    if (aa4[1] == aa4[3] - 2)
    {
        findmissing(aa4, u);
    }
    for (int i = 0; i < v; i++)
    {
        aa5[i] = Integer.parseInt(five[i]);
    }
    if (aa5[1] == aa5[3] - 2)
    {
        findmissing(aa5, v);
    }
    in.close();
}

public static void findmissing(int[] bb, int value)
{
    for (int i = 0; i < value - 1; i++)
    {
        if (bb[i] == bb[i + 1] - 1)
        {

        } else {
            System.out.println(bb[i + 1] - 1);
        }
    }
}

Answer 1

If (as I assume) the numbers are listed in order, then a very simple algorithm will work:

• For each possible digit-length 1 <= d <= 5 of the first number:
  • Call try(toInt(S[1 .. d]), S[d+1 .. |S|]) to try the sequence of numbers beginning with the number encoded by S[1 .. d]. If this sequence "works", output it and stop.

The main loop above stops at d = 5 because you give the constraint that M <= 99999, but it can easily be made to work with arbitrarily large numbers, simply by letting d increase all the way up to |S|.

The second step ("Try...") is easy, since you already have the first number x in this (candidate) sequence, so you can easily generate the digit-string corresponding to the number that should appear next (i.e., corresponding to x+1) and compare it with the remainder of S. If the digit-string corresponding to x+1 does not match the first few characters of S, then try the digit-string corresponding to x+2. If that matches, then set a flag recording the fact that x+1 is potentially the missing number, and carry on. If both x+1 and x+2 mismatch, or if x+1 mismatches and the flag is already set, we know that the initial value can't have been right, so return and let the main loop try the next longer initial number:

try(x, S):
    x1str = asString(x + 1)
    x2str = asString(x + 2)
    missing = -1        # Flag value to indicate "not found"
    while |S| >= |x1str|:
        if S[1 .. |x1str|] = x1str:
            Delete first |x1str| characters of S
            x = x + 1
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else if S[1 .. |x2str|] = x2str and missing = -1:
            Delete first |x2str| characters of S
            missing = x + 1
            x = x + 2
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else
            return -1    # Flag value to indicate "invalid sequence"
    if |S| > 0 then return -1    # Some gunk was left over
    return missing

Obviously you can replace the "Delete first ... characters of S" steps with just using an offset into the (unchanging) string, but I felt the above was easier for an explanation.