Finding the smallest integer which is not in an array [duplicate]

Question

Given an unsorted set A what is the most efficient solution for finding the smallest integer x which is not element of A such that x needs to be larger than some integer m?

e.g.

Input: A = {7, 3, 4, 1}, m = 5

Output: x = 6

I'm searching for solution in C, but any kind of pseudocode would be helpful... Can this problem be solved in O(n) where n is the set size?

Answer 1

I solved it using and extra array.Here 'len' is length of the array.

int findMin(int *arr,int n,int len)
{
    int *hash;
            if(len==0)
               {return -1;  //fail 
                }
    hash=(int*)calloc(len,sizeof(int)); //hash function I'm using is f(x)=f(x)-n;
    int i;
    for(i=0;i<len;i++){
        if(arr[i]>n && arr[i]<len+n){  //because max element can't be more than n
            hash[arr[i]-n]++;
        }
    }

    i=1;
    while(i<len){
        if(hash[i]==0)
            return len+i;
        i++;
    }
            return len+n+1;
}

The order of this soultion is O(n) running time and O(n) space.

Answer 2

The following Java code should work for you:

public static int findMinNotInArray(int array[], int n) {
    int frequency[] = new int[array.length];

    if (n < max(array)) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] > n && array[i] < n + array.length)
                frequency[array[i] - (n + 1)]++;
        }

        for (int i = 0; i < frequency.length; i++) {
            if (frequency[i] == 0)
                return i + n + 1;
        }
        return -1;
    } else {
        return n + 1;
    }
}

public static int max(int array[]) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

The above code simply tracks the numbers from n+1 to the (n+1) + lengthOfA whether any one from this range is present in the array or not! And returns the first non-present number!