Find Missing Number In String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in companies
AdobeOLX GroupAmazon

Problem statement

You had a sequence of consecutive nonnegative integers. You appended all integers at the end of each other to form a string ‘S’ without any separators. While appending each integer in a string, you forgot to append exactly one integer from the sequence. Now all the integers from a string and you don’t know which integer you have missed.

For example sequence 11, 12, 13 may form a string (without any separators) “1113” if you miss 12.

Your task is to find the missing number in the string such that it is possible to obtain a sequence of consecutive non-negative integers from the given string. If more than one missing integer is present or all the integers are already present or if the string is not valid then the answer will be -1 for all such cases.

Note: 
1. The string consists of only digits 0 to 9.
2. The numbers will have no more than six digits.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The only line of each test case contains a string of numbers 'S'.
Output Format:- 
For each test case, print a single line containing a single integer denoting the missing number.

The output of each test case will be printed in a separate line.
Note: 
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= |S| <= 10 ^ 4
0 <= S[i] <= 9

Where |S| denotes the length of the given string 'S' and S[i] is the digit at index i.

Time Limit: 1 sec.
Sample Input 1:
2
89101113
9899101102
Sample Output 1:
12
100
Explanation of the Sample Input1:
Test case 1:

If we divide the string in numbers, we can see that 8 9 10 11 13 form a consecutive set of numbers, however with 12 missing.

Test Case 2:-
If we divide the string in numbers we can see that 98 99 101 102 form a consecutive set of numbers, however with 100 missing.
Sample Input 2:
2
012
12131
Sample Output 2:
-1
-1
Hint

Try to check all combinations if they are consecutive or not.

Approaches (1)
Brute Force
  • The idea is to try all lengths from 1 to 6 for the first number of the sequence.
  • For each length, we check if the current length satisfies the property of all consecutive numbers except one missing number.
  • For each length ‘k’ where 1 <= k <= 6 we take the first ‘k’ characters of the string and assume it to be our first number of the consecutive sequence.
  • Now if the first number is ‘x’ then we want our next consecutive number to be ‘x + 1’. We traverse the string from index ‘k’ and match each character with the digits of number ‘x + 1’ if we found all characters are matched with all digits of ‘x + 1’ that means we found our second number of sequence and similarly we check for ‘x + 2’ and so on.
  • If at any point we found that characters are not matching with our digits that means this current number that we are trying to find in our string will be our missing number but we must check that after missing number all the remaining numbers should form a consecutive sequence.
  • If all the numbers are not forming the consecutive sequence then we try for the next length until we find our correct answer.
  • Note: If all numbers are in consecutive sequence then the next number of the sequence will be our missing number.
Time Complexity

O(N), where ‘N’ is the size of the string.


We are visiting every digit at max of six times in the string.

Space Complexity

O(1).

 

Since we are using constant space. 

Code Solution
(100% EXP penalty)
Find Missing Number In String
Full screen
Console