6

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?

Slaven Glumac
  • 543
  • 9
  • 19

3 Answers3

6

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.

banarun
  • 2,305
  • 2
  • 23
  • 40
3

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!

Sazzadur Rahaman
  • 6,938
  • 1
  • 30
  • 52
1

I think, the most feasible approach is to sort the array first. Then you can do a binary search for m in it, followed by a linear search for the next point where neighbours are more than one apart.

Complexity of this approach is that of the sorting algorithm, which is to say O(nlogn) in most cases.

cmaster - reinstate monica
  • 38,891
  • 9
  • 62
  • 106
  • 1
    Why would you sort it first? You could just iterate once over the array, make a (if(a[i] pivot) min_so_far=a[i])? Thats take O(n), you need to go once over the array, thats it. Sorting is O(n log n), which is more. – SinisterMJ Jun 30 '13 at 15:13
  • You have to take into account, that there is an apparent gap, that gets filled only later. Like this: {0, 2, 3, 4, 1} and m=0. You have to return 5 in this case, and you don't want to try 1, 2, 3, 4 sequentially because that would mean O(n*n). That is, why I would sort first. – cmaster - reinstate monica Jun 30 '13 at 15:20
  • 1
    @AntonRoth: You need to find a value that is *not* in the array. Your approach would work for finding a value which is in the array. – interjay Jun 30 '13 at 15:22
  • Ah, okay, misread the question. That makes sense then. – SinisterMJ Jun 30 '13 at 15:30