Hacker News new | ask | show | jobs
by yobbo 1481 days ago
It's a quiz problem, and it's supposed to have "trick" solutions.

However, if he wants to play that game, he should provide proof of his solution, not fiddle with syntax or error checking. That's why discussion is more important, and how he can show that understands what he's doing and not just memorizing tricks. (... none of which matters for his future role anyway.)

The formula "falls out" naturally if you're used to working with summations:

Σi = Σ(n-i+1) = n² - Σi + n

2Σi = n² + n

... but the xor solution is more elegant.
3 comments
er888kh 1481 days ago
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.

link
Karliss 1481 days ago
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.

link
yobbo 1481 days ago
xor will not overflow and is obviously correct.

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

link
visarga 1481 days ago
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).

link