help me to create this algorithm

[-EquinoX-]

An array A contains n -1 unique integers in the range [0, n-1], that is, there is one number from this range that is not in A. Design an O(n) -time algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself.

[legend986]

You can do it as follows:

S1= Sum up all the integers from 0 to n-1
S2 = Sum up all the integers that belong to the array
Then, S1-S2 will give you the missing integer.

[-EquinoX-]

can you explain why this is possible with an example?? I can't seem to understand this..

[legend986]

Oh I'll wait for the algo gurus here to give a better solution but the explanation goes somehting like this:

Suppose that your array has these elements: 1, 2, 4, 3, 6
Its clear that 5 is missing. Now lets try getting it:
We know that the array should be having numbers from 1 to 6 but the question says that one is missing and that all are unique.
So, we sum up 1 to 6 which is 1+2+3+4+5+6
Now, sum up the elements in the array: which is 1+2+4+3+6

Subtract these two sums: (1+2+3+4+5+6) - (1+2+4+3+6) = 5
And that is what we are looking for. This method fails if the numbers aren't unique though. But anybody, please feel to correct me if I'm wrong. :)

[-EquinoX-]

can you give me an example for when this fails?

[legend986]

When the elements of the array are not unique...

[-EquinoX-]

what do you mean unique here?

[legend986]

The array elements aren't like 1,1,1,2,3,4,5 and because the question says unique integers you're safe with this technique I guess...

[ProgramThis]

If you can only use O(1) additional space it seems to me that you can only use one variable to perform this, is that correct?

If so you'll need to sum the numbers from 1 to n-1, then subtract your answer by all of the elements in the array. If the O(1) is refering to the number of variables that you can use, then you can't add S1, add S2 then subtract S1 - S2.

[KRUNCH]

well actualy he can
he can just use nand set it like
n=n*(n-1)/2
to get sum of all the integers to the number n-1;
now in a loop like

for i=1 to n-1 i++
{
n-=array[i];
}
// here n is the result , implent it in youre program and thats it
there is no algo guruing about this one this is plain maths