Algorithm in C# : In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?

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. 

Method 1:

Method 2:

 

Tagged with: ,
Posted in Algorithm, C#

Categories

Related Posts