algorithm - Given numbers from 1 to 2^32-1, one is missing. How to find the missing number optimally?

Question

You are given 2^32-2 unique numbers that range from 1 to 2^32-1. It's impossible to fit all the numbers into memory (thus sorting is not an option). You are asked to find the missing number. What would be the best approach to this problem?

---

Let's assume you cannot use big-integers and are confined to 32bit ints.

ints are passed in through standard in.

Answer 1

Major Edit: Trust me to make things much harder than they have to be.

XOR all of them.

I'm assuming here that the numbers are 1 to 2³² - 1 inclusive. This should use 1 extra memory location of 32 bits.

EDIT: I thought I could get away with magic. Ah well.

Explanation:

For those who know how Hamming Codes work, it's the same idea.

Basically, for all numbers from 0 to 2ⁿ - 1, there are exactly 2^{(n - 1)} 1s in each bit position of the number. Therefore xoring all those numbers should actually give 0. However, since one number is missing, that particular column will give one, because there's an odd number of ones in that bit position.

Note: Although I personally prefer the ** operator for exponentiation, I've changed mine to ^ because that's what the OP has used. Don't confuse ^ for xor.