What's the optimal way to calculate which integer in a list is missing?

Question

I was recently in an interview where they asked me technical questions. One was how you would calculate which number in a list of length n-1 was missing. The list contained every number from 1 to n, except i where 1 <= i <= n. The numbers were not in order. My solution was to add them all up, then subtract that from the calculation of the numbers from 1 to n, by adding 1 to n and multiplying by n/2 or (n-1)/2 as appropriate. But I got the sense that there was a better way to do it. What is the optimal solution?

Answer 1

Your answer is good enough, in my opinion.

But some people -- perhaps your interviewer is one of them -- are worried about overflow and such. In that case, use XOR instead of addition.

To obtain the XOR of the integers from 0 to n, just XOR together the array indices as you loop. Given the XOR of the integers from 0 to n, and the XOR of the array elements, you just XOR the two of those together to get the missing element.

P.S. The sum of the integers from 1 to n is always (n+1)*n/2