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

Add all the numbers you are given up using your favourite big integer library, and subtract that total from the sum of all the numbers from 1 to 2^32-1 as obtained from the sum of arithmetic progression formula

Answer 2

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.

Answer 3

Use bitwise operator XOR. Here are example in JavaScript:

var numbers = [6, 2, 4, 5, 7, 1]; //2^3 exclude one, starting from 1
var result = 0;

//xor all values in numbers
for (var i = 0, l = numbers.length; i < l; i++) {
    result ^= numbers[i]; 
}

console.log(result); //3

numbers[0] = 3; //replace 6 with 3
//same as above in functional style
result = numbers.reduce(function (previousValue, currentValue, index, array) {return currentValue ^= previousValue;});

console.log(result); //6

The same in C#:

int[] numbers = {3, 2, 4, 5, 7, 1};

int missing = numbers.Aggregate((result, next) => result ^ next);

Console.WriteLine(missing);

Answer 4

Assuming you can get the Size() you can use some binary approach. Select the set of numbers n where n< 2^32 -2 / 2. then get a count. The missing side should report a lower count. Do the process iteratively then you will get the answer