Finding the smallest integer which is not in an array

algorithm, arrays, c

Solution

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.

Problem

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?

Original source

Related problems