Pretty easy.
Compare the sum with the expected sum. Compare the sum of squares with the expected sum of squares.
Two equations, just solve them. I wrote the final equations in the blog comments.
Compare the sum with the expected sum. Compare the sum of squares with the expected sum of squares.
Two equations, just solve them. I wrote the final equations in the blog comments.
You could do this solution using the field of bitfields modulo a 64-bit irreducible polynomial, but I expect that's over the heads of most interviewers :P
(edit: just realized that you can do the neccesary field multiplication and addition very quickly in constant time and space. It's even linear in the number of bits you have to process. This looks very close to an ideal solution, so I posted a link on the blog. There may be a clever solution that is better.)
(edit #2: the clever solution is just to use bigints. The sum of squares is guaranteed to fit in 192 bits. This might be what the parent poster meant all along. This works because integers are a factorial ring, so the equations are guaranteed to have a unique solution.)
I was kinda expecting the bigint solution though.
-- Max
Scan over the array accumulating two quantities.
P <- P*arr[i]/i; % prod(arr)/N!
Q <- Q + i - arr[i]; % (N/2)(N+1) - sum(arr);
You could conceivably compute P in log terms as well to make it a bit more stable if needed.