Help Dr. Wu

This problem can be solved in O(NlgN) by a single pass on the entire array.

For each index i, where i > 0, the value of the input array a[i] needs to be subtracted from a[i-1] to get the number that was mentioned at index i. For i=0, a[0] is itself the number that was mentioned by the participant. This step can be completed in O(N).

The N numbers that were found in the previous step can be kept in a built-in data structure to check if all the numbers are unique. The uniqueness of the numbers can also be determined by keeping the number found in the previous pass in an array and sorting the array. Whether a built-in set or map like data structure is used, or the sorting of the array is used, the complexity of this step will be O(NlgN).