#codingexercise
A very common coding question is to find the duplicate in an array of n+1 numbers with values ranging from 0 to n. This problem has many variations and different solutions depending on the requirements. We will list some of these here.
The problems can vary in the following ways:
1) exactly one number appears in duplicate
2) more than one number appears in duplicate
3) number of elements in the array may be large
4) any number can appear any number of times

The solutions can vary depending on whether the
1) elements can be sorted
2) auxiliary storage is available
3) optimize for both storage and computation
4) solutions based on indices

Let us discuss a few approaches:
1) The O(n^2) approach
List<int> duplicates = new List<int>();
for (int i = 0; i < n; i ++)
    for (int j = i + 1; j < n; j ++)
        if A[i] == A[j] && duplicates.Contains(A[I]) == false
            duplicates.Add(i);
return duplicates;

2) The HashTable approach that uses a frequency count
    for (int i = 0; i < n; i++)
         H[i] += 1;

    foreach (var item in H)
        if H[i] > 1
              print H[i];

3) The linear scan approach when the elements are sorted:
      sort (A);
      curSum = 0;
      for (int i = 0; i< N; i ++)
           curSum += A[i];
      return sumofduplicates = n(n+1)/2 - CurSum;

4) If we are able to modify the array, one innovative example that appears in internet is to flip the sign of an element. And the next time we see a flipped sign we know it is a duplicate.
This works like this:

Traverse the array. Do following for every index i of A[].

{

check for sign of A[abs(A[i])] ;

if positive then

   make it negative by   A[abs(A[i])]=-A[abs(A[i])];

else  

   this   element (ith element of list) is a repetition

}