Senior Unix/C++ Developer - Tradebook Interview
Sequence of numbers in random order and 1 of them is missing how to find that out...
If the sequence is guaranteed to contain only positive integers, it can be done like so: Read in the sequence, noting the MIN and MAX numbers. The sum IF it started from 1 would be MAX(MAX-1)/2. The sum of the 'missing' numbers (from 1 up to where the sequence actually starts) is (MIN-1)*MIN/2. The missing number is given by taking the difference between the two: X = [MAX*(MAX-1) - (MIN-1)*MIN]/2.
Oops, in addition to what I put above there is a final step to get the actual answer. The missing number is equal to X minus the sum of the numbers given.
N(N+1)/2 - sum of the input = missing number
It isn't stated that sequence starts from 1. The sequence could be 8,9,5,6!