Interview Question for Senior Software Engineer at Apple:

This felt like a brain teaser question to me, and since I hadn't heard it before it took me a little while to come up with a solution that involved using a factorial function.

You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer.

Heres an explanation, http://www.techinterview.org/post/526329049/sum-it-up

int sum = 0;
int xorSum = 0;
for(int i =0 ; i < n; i++)
{
   sum += input[i];
   xorSum ^= input[i]
}
return (sum - xorSum)/2;