Find missing element

I saw the following question:

Given an array A of integers, find an integer k that is not present in A. Assume that the integers are 32-bit signed integers.

How to solve it?

Thank you

//// update -- This is the provided solution - but I don't think it is correct //// Consider a very simple hash function F(x)=x mod (n+1). we can build a bit-vector of length n开发者_JAVA百科+1 that is initialized to 0 and for every element in A, we set bit F(A[i]) to 1.Since there are only n elements in the array, we can find the missing element easily.

I think the above solution is wrong.

For example, A [ 2, 100, 4 ], then both 4 and 100 will match to the same place.

If I'm interpreting the question correctly, (find any integer not in A) and n is the number of elements in A, then the answer is correct as given.

The fact that the hash function can have collisions doesn't really matter; By the pigeonhole principle in reverse, there will be some bit in the bit vector that is not set - because it has more bits than there are elements in A. The corresponding value is an integer not in A. In the case where the hash function has collisions, there will actually be more than one bit not set, which works in favor of the algorithm's correctness rather than against it.

To illustrate, here's how your example would work out:

A = [2, 100, 4]
n = length(A) = 3
f(x) = x mod 4
map(f,A) = [2, 0, 0]

so the final bit vector will be:

[1,0,1,0]

From there, we can arbitrarily choose any integer corresponding to any 0 bit, which in this case is any odd number.

max (items) + 1

springs to mind. Of course it would fail if one of the elements was 2^31-1 and another was -(2^32).

Failing that, sort them and look for an interval.

Since there appear to be no upperbounds or other constraints:

for (int i = int.MinValue; i <= int.MaxValue; i++)
{
    if (! A.Contains(i))
    {
       // found it !
       break;
    }
}