Find the missing number in sequence given as string

Concepts Used:

String

Difficulty Level:

Medium

Problem Statement (Simplified):

Find the missing number in a given in a series as a string with no separator. The maximum length of the number can go up to 6 only. Print -1 if the sequence is invalid, or sequence skips number more than 1 place.

See original problem statement here

Test Case:

    Input:
    4
    1234578
    1314151618
    123124125127
    1213141718

    Output:
    6
    17
    126
    -1

    Explanation:
    Case-1:
        Given sequence is "1 2 3 4 5 7 8" where 6 is missing from sequence, so 6 is our answer.
    Case-2:
        Given sequence is "13 14 15 16 18" where 17 is missing from sequence, so 17 is our answer.
    Case-3:
        Given sequence is "123 124 125 127" where 126 is missing from sequence, so 126 is our answer.
    Case-4:
        Given sequence is "12 13 14 17 18" where 6 and 7 are missing from sequence, gap can be only of one number so it is an invalid sequence, so -1 is our answer.

Solving Approach :

1) As we know the maximum length of the number goes up to 6, so we can check the number of all lengths from 1 to 6.
2) For each length, we convert numbers of length from string to integer and check if any number is missing from the sequence, if yes we print the number.
3) If the sequence has more than 1 number missing or number have a difference more than 1, that means sequence is invalid. So, we print -1 in this case.
4) Exceptions occur when the number of digits changes when moving to the next number, for example moving from 99 to 100, we use log₁₀A values in such cases, to notice the change in digits.

Example:

• Test Case – 1:

  Let string s = "12356",
  Finding all values of length 1 first,
  converting all digits of length 1 in number, we get these values,

  1,2,3,5,6

  As we can see 4 is missing, we print 4 as our result, and we don’t need to check further.

• Test Case – 2:

  Let string s = "1112131516",
  Finding all values of length 1 first, we get these values,
  1,1,1,2,1,3,1,5,1,6
  As we can see this series does not make a sequence, we check for all numbers of length 2, Thus, we get this >sequence,
  11,12,13,15,16
  As we can see, this sequence lacks 14, hence 14 is our answer and we do not proceed further.

• Test Case – 3:
  Let string s = "9899100102"
  We start checking for all values of length 1, thus we get this sequence,
  98,99,10
  While reading 10 we get the value of $log_{10}(10)$ which is 1, meaning length has to be increased by 1, and from here we check for number with length 2+1 i.e. 3, hence the sequence becomes,
  98,99,100,102
  We can see this sequence lacks 101, so we print 101 as our answer.

Solutions

#include 
#include 
#include

int len = 0;

int getValue(char str[], int i, int m) 
{ 
    if (i + m > len) 
        return -1; 

    int value = 0; 
    for (int j = 0; j < m; j++) 
    { 
        int c = str[i + j] - '0'; 
        if (c < 0 || c > 9) 
            return -1; 
        value = value * 10 + c; 
    } 
    return value; 
} 

int findMissingNumber(char str[]) 
{ 
    for (int m=1; m<=6; ++m) 
    { 
        int n = getValue(str, 0, m); 
        if (n == -1) 
        break; 

        int missingNo = -1; 

        int fail = 0; 

        for (int i=m; i!=len; i += 1 + log10(n)) 
        { 
            if ((missingNo == -1) && 
                (getValue(str, i, 1+log10(n+2)) == n+2)) 
            { 
                missingNo = n + 1; 
                n += 2; 
            } 

            else if (getValue(str, i, 1+log10(n+1)) == n+1) 
                n++; 

            else
            { 
                fail = 1; 
                break; 
            } 
        } 

        if (fail==0) 
        return missingNo; 
    } 
    return -1;
} 

int main() 
{ 
    int test;
    scanf("%d",&test);

    while(test--){

        char str[1001];
        scanf("%s",str);

        len = strlen(str);

        printf("%d\n",findMissingNumber(str));

    }
}

#include 
using namespace std; 

int len = 0;

int getValue(char str[], int i, int m) 
{ 
    if (i + m > len) 
        return -1; 

    int value = 0; 
    for (int j = 0; j < m; j++) 
    { 
        int c = str[i + j] - '0'; 
        if (c < 0 || c > 9) 
            return -1; 
        value = value * 10 + c; 
    } 
    return value; 
} 

int findMissingNumber(char str[]) 
{ 
    for (int m=1; m<=6; ++m) 
    { 
        int n = getValue(str, 0, m); 
        if (n == -1) 
        break; 

        int missingNo = -1; 

        bool fail = false; 

        for (int i=m; i!=len; i += 1 + log10l(n)) 
        { 
            if ((missingNo == -1) && 
                (getValue(str, i, 1+log10l(n+2)) == n+2)) 
            { 
                missingNo = n + 1; 
                n += 2; 
            } 

            else if (getValue(str, i, 1+log10l(n+1)) == n+1) 
                n++; 

            else
            { 
                fail = true; 
                break; 
            } 
        } 

        if (!fail) 
        return missingNo; 
    } 
    return -1;
} 

int main() 
{ 
    int test;
    cin>test;

    while(test--){

        char str[1001];
        cin>str;

        len = strlen(str);

        cout<
						 

import java.util.*;
import java.io.*;

public class Main {

  static int len = 0;

  static int getValue(String str, int i, int m){ 
      if (i + m > len) 
          return -1; 

      int value = 0; 
      for (int j = 0; j < m; j++){ 
          int c = str.charAt(i + j) - '0'; 
          if (c < 0 || c > 9) 
              return -1; 
          value = value * 10 + c; 
      } 
      return value; 
  } 

  static int findMissingNumber(String str) 
  { 
      for (int m=1; m<=6; ++m) 
      { 
          int n = getValue(str, 0, m); 
          if (n == -1) 
          break; 

          int missingNo = -1; 

          int fail = 0; 

          for (int i=m; i!=len; i += 1 + (int)Math.log10(n)) 
          { 
              if ((missingNo == -1) && 
                  (getValue(str, i, 1+(int)Math.log10(n+2)) == n+2)) 
              { 
                  missingNo = n + 1; 
                  n += 2; 
              } 

              else if (getValue(str, i, 1+(int)Math.log10(n+1)) == n+1) 
                  n++; 

              else
              { 
                  fail = 1; 
                  break; 
              } 
          } 

          if (fail==0) 
          return missingNo; 
      } 
      return -1;
  } 


  public static void main(String args[]) throws IOException {

    Scanner sc  = new Scanner(System.in);
      int test = sc.nextInt();

      while(test-->0){

          String str = sc.next();

          len = str.length();

          System.out.println(findMissingNumber(str));

      }

  }
}

[forminator_quiz id="867"]

This article tried to discuss the concept of String. Hope this blog helps you understand the concept of string. To practice more problems you can check out MYCODE|competitive programming