Find Missing Number In String
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

Question

Find Missing Number In String

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.

Accepted Answer

XOR approach can be used to solve this question in an efficient manner. The following property of XOR can be used :
1. If x1^x2^…xn = a and x1^x2^..xn-1 = b , then a^b = xn
Steps:
1. Declare two variables a= 0 and b = 0
2. Calculate the xor of numbers from 1 to n and store them in a i.e. 1^2^…n = a.
3. Now traverse the array from start to end.
4. For every index i update b as b = b ^ arr[i]
5. Return the missing number as a ^ b.
Time Complexity : O(N)
Space complexity : O(1)

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are using constant space.

Time Complexity: O(1)Explanation:

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

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

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

Note:

Input Format:-

Output Format:-

Note:

Constraints:

Top UBS ENO interview questions & answers

Top HR questions asked in UBS ENO