Last Updated: 25 Dec, 2020
Find Missing Number In String
Moderate
Asked in companies
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.
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.
Approaches
- 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.