I came up with another solution (which is purposefully complicated): It is known that the sum of n-th roots of unity is zero. So if we choose the n-th roots of unity as ω and calculate Σ ω^ai, the result should be 0 + ω^(the duplicate number).

So I opened the python interpreter, and I used this very trivial method of calculation (instead of summing the sine and cosine functions independently), and using asin and acos functions, got the result. It turned out to be accurate for n=1e6 with an error of ~1e-5. So it should be usable for much bigger n too.

In my view the trick in this question is to think about adding up numbers not how you add them up.Since this was a programming question you don't need to know the formula you can add up the numbers in a loop. It wouldn't even be much slower since you need a loop of size N anyway for the purpose of adding up numbers in the input.

Xor solution and adding solutions are the same solution it's just a matter of what binary function you use for calculating sum. You can use any commutative, associative binary function which has inverse. You can use addition, xor or even multiplication.

xor will not overflow and is obviously correct.

I'm not sure modulus-addition would be correct.

I learned this formula before high school. It was considered trivial.

The demonstration was to write the sums 1+2+...N and N+(n-1)+...+1 and add them up position wise. The sum comes n*(n+1)/2 (divide by 2 for the two sums).