CareerCup

Adding up all numbers as mentioned by S is good but cannot be implemented as addition of so many numbers will result in overflow..

Instead, all numbers can be xored...

ie
for numbers 1..5,
(1^2^3^4^5) ^ (3^4^1^5) will give the missing number 2

ANSWER: add up the sum of all expected values, then subtract the sum of all values in the array and you have your missing number. O(n) runtime.

use bitmap

check programming pearls, chapter 1. Binary method

What is the Binary method?

boolean bools(1..1 million)
foreach element e in bools
e = false
endfor

foreach element e in array
bools(e) = true
endfor

foreach element e in bools
if e equals false
println "THE MISSING NUMBER IS ", e
endif
endfor

Above technique can be used to find out not just 1 but several missing numbers. It works even if original array has all numbers missing!

if the number are in sorted order and, we know the lengh, we can find with in O(log(n)) complexty

keep deviding the length and number with 2, and verify lengh of both partitions.

Yes, doing a XOR is a good option.

Here is a (hopefully) fun puzzle related to this.

Give a formula for 1 XOR 2 XOR 3 XOR .... XOR n.

Basically, give a constant time algorithm to calculate the XOR of first n natural numbers.

The XOR solution will work only if N (the total number of numbers) is of the form 2^K-1.

Of course we can always find the number 2^K-1 >= N and implicitly treat them as present

cocoler has de right soln

*coboler

We make use of the XOR operator as follows:

axor = the n values in the array (a[0]^a[1]^...^a[n-1])
vxor = the consecutive values from 0 to n (n+1 values) (0^1^...^n).

At the end axor^vxor gives the missing number since all other numbers cancel each other out.

int missingNumber(int *a, int n)
{
	int axor=0, vxor=n;
	for(int i=0; i<n; i++)
	{
		axor ^= a[i];
		vxor ^= i;
	}
	return (axor ^ vxor);

}

Thanks!

How about:

(1):Bloom filter OR
(2): n(n+1)/2 formula

Using the xor technique we will get the missing number, find the xor of numbers 1 to 1 million and then find the xor of all array elements and then, finally find the xor both the previously xor elements.