Find the repeated element

There are n elements in an array, and one element is repeated n/2 times (n is even), and other n/2 numbers are unique. Find the element that is repeated n/2 times.

Simple Solution:

In the array, take the first element and compare with second and third. If it is same as any other, that is the answer. Otherwise, take the second element and compare with the third and fourth elements, and so on. There is only one exception in this. If the no.of elements is 4, and if the input is like a, b, c, a, then this solution will not work. In that case, For the last two elements, we can compare with the first element or first two elements depending on whether it is last but one element or last element.

Optimum Solution:

The following gives the solution in n/2+2 comparisons

int FindRepeatedElement(int a[], int n)
{
 int i;
 for(i=0; i<n-1; i+=2) {
  if(a[i] == a[i+1])
   return a[i];
 }
 if(a[0] == a[2])
  return a[0];
 if(a[0] == a[3])
  return a[0];
 return a[1];
}