Given an array of N elements which contain numbers from 1 to N+1 in random order, each only once and one of them missing, find the missing number in the best way you can.
Let's first see with an example that we have understood the question correctly. The array size is say, N=5, it contains numbers from {1,2,..,6} each except one exactly once, in random order - e.g. {2,3,1,5,6}. Given this, we have to find the missing number i.e. 4 here.
This problem seems quite easy and indeed it is! You know beforehand what the value of N is and you can traverse the array one by one, keeping track of which element you have seen till now. This requires additional storage and setting of flags per element i.e. theta(N) space. But, logically this works correct. At the end, you emit that number for which the "saw it" flag is not set.
Can we somehow eliminate this extra storage? This needs some extra insight in the problem statement. What if I tell you, the array has numbers from {2,5,7,9,15} and one of them is missing. The above approach of setting flags will work here also as long as you know the numbers that you expect to see. So, what is the difference that makes original problem a special case of this generic problem? As you might have noticed, the given array has a nice property. The elements are not arbitrary chosen but they all come from {1,..N}. Now, in order to remove the need of extra space, one has to think of aggregating the results in some way. Thus instead of storing per value, one flag and setting it, can we aggregate the information we have seen so far? Such aggregation will eliminate extra space requirement. One obvious way to aggregate is : take sum. And here comes the above mentioned property handy! We know that sum of first N numbers can be easily calculated as given in
this. Call this S. Now traverse the array and keep the track of sum seen, call this S'. The missing number is S-S'!
