Missing integer variation - O(n) solution needed [closed]

Question

The problem comes from Codility programming training and it sounds as follows: we have an array (A[]) with n (ranging from 1 to 100,000) elements and these are our parameters. The elements of the array are integers from −2,147,483,648 to 2,147,483,647, and we need to find smallest positive integer that is NOT in the array. Of course this could be done easily in O(n*log n) by sorting them all and going through the sorted array, looking for the missing posiitve number (this last operation has O(n) worst time complexity in my solution). But according to Codility, this ENTIRE problem can be done in O(n), and I cannot see any way to do that. Could someone give some tips to let me get un-stuck?

PS Here is a link to detailed description of the problem which I'm not allowed to copy - https://codility.com/c/intro/demo35UEXH-EAT

Answer 1

By pigeonhole principle, at least one of the numbers 1, 2, ..., n+1 is not in the array. Let us create a boolean array b of size n+1 to store whether each of these numbers is present.

Now, we process the input array. If we find a number from 1 to n+1, we mark the corresponding entry in b. If the number we see does not fit into these bounds, just discard it and proceed to the next one. Both cases are O(1) per input entry, total O(n).

After we are done processing the input, we can find the first non-marked entry in our boolean array b trivially in O(n).

Answer 2

Simple solution 100% in Java.

Please note it is O(nlogn) solution but gives 100% result in codility.

public static int solution(final int[] A) 
{   
   Arrays.sort(A);
   int min = 1;

   // Starting from 1 (min), compare all elements, if it does not match 
   // that would the missing number.
   for (int i : A) {
     if (i == min) {
       min++;
     }
   }

   return min;
}

Answer 3

wrote this today and got 100/100. not the most elegant solution, but easy to understand -

public int solution(int[] A) {
    int max = A.length;
    int threshold = 1;
    boolean[] bitmap = new boolean[max + 1];

    //populate bitmap and also find highest positive int in input list.
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0 && A[i] <= max) {
            bitmap[A[i]] = true;
        }

        if (A[i] > threshold) {
            threshold = A[i];
        }
    }

    //find the first positive number in bitmap that is false.
    for (int i = 1; i < bitmap.length; i++) {
        if (!bitmap[i]) {
            return i;
        }
    }

    //this is to handle the case when input array is not missing any element.
    return (threshold+1);
}