Suppose In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?

Submitted by: Muhammad
This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2) which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.
Submitted by: Muhammad

Read Online Data Structure Linked list Job Interview Questions And Answers