[cynicalkane]

You can't solve these equations (at least in the general case, maybe there's some clever way in this specific case I'm not getting), because the ring of 64-bit integers is not a factorial ring, meaning not every multiplication can be undone. That is, if xy = z, there might be multiple y's for a given x and z. (Edit--previously I had said it's because it's not a field, but that's a stronger condition than we need.) If the sum is 2 and the sum of squares is 0, then (1, -1) and (2^63 + 1, 2^63 - 1) are both solutions.

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.)

[mschireson]

Simpler to do the arithmetic modulo a prime just smaller than 2^64 if you ignore the case where n is very close to 2^64 (which should be fine in real life). In case you leave your code will be easier to maintain than if you bring Galois Fields into it.

I was kinda expecting the bigint solution though.

-- Max