This question is a remix of the one that I made previously on this forum. The only difference with this one is: the range is significantly larger, AND dynamic. Details below!
Also, I'm typing this question incredibly quickly, so if there are any grammatical errors, I do apologize and ask if anyone would edit the question to clear any vagueness. Nonetheless, the original question is posted here: The Missing Number Revised
Given a minimum bound M, a maximum bound N, and a String of randomly concatenated integers [min, max), min (M) to max (N) exclusive, there is a number missing in the sequence. Your job is to write a program that will calculate this missing number.
Doing this problem by hand on smaller Strings, such as examples 1 and 2 below are obviously very easy. Conversely, computing a missing number on incredibly large datasets involving three-digit, four-digit, or more numbers would be incredibly difficult. The idea behind this problem is to construct a program that will do this process FOR you.
One thing that appeared as rather confusing when I posted this problem last night was: what exactly a missing number is defined as. A missing number is the number INSIDE of the range specified above; NOT necessarily the digit. In example 3, you will see that the missing number is 7, even though it appears in the sequence. There are 3 places the DIGIT 7 will appear in a series of [0, 30): “7”, “17”, and “27”. Your objective is to differentiate between these, and discover that 7 is the missing NUMBER (inside of example 3). In other words, the tricky part lies in finding out which sequences of digits are complete and which belong to other numbers.
Another very important factor in this: there are some input situations where there are multiple solutions! Your job will be to print out ALL numbers that are missing in the sequence. I cannot provide insight as to WHY they have multiple solutions; I only know they may exist.
The input is a single Integer T: the amount of test cases.
For each test case, there is an Integer M: the minimum number in the sequence, another Integer N: the maximum number in the sequence (thus M < N at ALL times), a String S, containing integers from M to N - 1 inclusive, or M to N exclusive (in other words, [M, N)). These integers, as stated above, are scrambled up to create a random sequence. There are NO delimiters (“42, 31, 23, 44”), or padding 0’s (003076244029002); the problems are exactly as described in the examples.
As stated above, M is ALWAYS lower than N, and the maximum range of numbers is < 100,000. |N - M|.
Whoever has the fastest, and lowest memory usage will be the winner. In the miraculous event that a time ties, lower memory will be used for the time breaker. Please list Big O if you can!
(Examples 1-6 are just for demonstration. Your program needn't to handle them.)
Please keep in mind the way you're to read in the data: Digit D represents how MANY test cases there are, the next lines will follow with integers M and N, then String S. I just wanted to clear it up. I also apologize for the incredibly large pastebin. Good luck!