Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number?
Very often the so called "smart" answer to this question is to sum it up and find the difference from the expected sum. But why not just walk through the list and check the number before it? Both are O(n). Am I missing something?
The "smart" answer is the best solution when the list is not sorted, because it visits each element only once and uses O(1) additional space. If the list is sorted, there is even a O(log n) solution: You can do a binary search. By looking at the central element, you can see if the duplicate number is before or after that element and continue bisecting until you found it.
Example:
1 2 2 3 4 5 6
The central element is 3, but it is in the fourth position, so the duplicate must be before it. Next check is the 2 in second position, so we have to look after the second position etc.
If the numbers are sorted, then you're not missing anything.
To know the misterious number x you only need to sum all the numbers in the sequence:
S = sum(sequence)
S = sum(from 1 to (n - 1)) + x
sum(from A to B) = 1/2 * (A + B) * (B - A + 1)
sum(from 1 to (n - 1)) = 1/2 * (1 + (n - 1)) * ((n - 1) - 1 + 1) = 1/2 * n * (n - 1)
x = S - sum(from 1 to (n - 1))
x = S - 1/2 * n * (n - 1)
