Is there an O(n) algorithm to find the first missing number in an array?

Question

Given an array of n integers, not necessarily sorted, is there an O(n) algorithm to find the least integer that is greater than the minimum integer in the array but that is not in the array?

Answer 1

Given an array of n integers, without negative numbers, not necessarily sorted, is there an O(n) algorithm to find the least integer that is greater than the minimum integer in the array but that is not in the array?

This can be solved with O(N) time complexity, with N being the number of element in the array. Let us call that array a1, the algorithm is as follows:

1. Find the smallest value in a1 (i.e, min);
2. Create a new array a2 with size equals to N;
3. Initialized the array a2 with a value to signal missing element, for instance min - 1;
4. Iterate through the array a1, and for each position, take the element in that position e1 = a1[i], and only if e1 is not greater than min - N mark the corresponded position on a2 as visited, for instance using the element itself, namely a2[e1 - min] = e1; If e1 is greater than min - size then it clearly does not belong to the sequence, and can be ignored because in the worst-case scenario the first missing value will be the value min + N + 1.
5. Lastly, iterate through the array a2, and get the first element = -1; it will be your first missing element.

Steps 1, 3, 4, and 5, all of them take in the worst-case scenario N. Hence, this algorithm takes 4N, which is O(N) time complexity;

The code will be straight forward to implement; for instance something as follows (for an array {5, 3, 0, 1, 2, 6}):

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>

int find_min(int *array, int size){
    int min = array[0];
    for(int i = 0; i < size; i++)
        min = (array[i] < min) ? array[i] : min;
    return min;
}

void fill_array(int *array, int size, int missing_value){
     for(int i = 0; i < size; i++)
        array[i] = missing_value;
}

void mark_existing_values(int *s, int size, int *d, int min){
    for(int i = 0; i < size; i++){
        int elem = s[i];
        if(elem - min < size)
           d[elem - min] = elem;
    }
}

int find_first_missing_value(int *array, int size, int min){
     int missing_value = min - 1;
     for(int i = 0; i < size; i++){
         if(array[i] == missing_value){
            return i + min;
         }
     }
    return missing_value;
}


int main(){
    int array_size =  6;
    int array_example [] = {5, 3, 0, 1, 2, 6};
    int min = find_min(array_example, array_size);
    int *missing_values = malloc(array_size * sizeof(int));
    fill_array(missing_values, array_size, min - 1);
    mark_existing_values(array_example, array_size, missing_values, min);
    int value = find_first_missing_value(missing_values, array_size, min);
    printf("First missing value {%d}\n", value);
    free(missing_values);
    return 0;
}

OUTPUT:

First missing value {4}

This algorithm works also for negative numbers, for instance if int array_example [] = {-1, -3, 0, 3, 5, 6, 7, 8, 10};, then the output would be:

First missing value {-2}    

The code can be simplified if in step 3 and step 4 instead of min - 1 and a2[e1 - min] = e1, respectively, we use two flags to signal missing (e.g., 0) and existing values (e.g., 1). Just like showcase in @Damien code. The downside is that we are using two flags instead of one. The benefit is that it simplifies the code, and in case the smallest value in the array is the smallest value that can be represented in C we will not underflow with min - 1.

Answer 2

The following algorithm has a complexity O(n).

I will assume here that the missing element must be selected after the minimum value.
The algorithm can be easily modified if the minimum possible value is fixed, for example equal to 0.

Once we have determined the minimum value a (in O(n) or in O(1) if the value is known in advance), then we know that the missing value is less or equal a + n, if n is the array size.

Then we simply have to use an array of size n+1, present[n+1], initialised to 0, and then to look at all values arr[i]:

if (arr[i] <= a+n) present[arr[i] - a] = 1;

Finally, in a third step we simply have to examine the array present[.], and seach for the first index k such that present[k]==0.

The first missing number is equal to a + k.

#include <stdio.h>
#include <stdlib.h>

int find_missing (int *arr, int n) {
    int vmin = arr[0];
    int *present = calloc (n+1, sizeof(int));
    for (int i = 1; i < n; ++i) {
        if (arr[i] < vmin) {
            vmin = arr[i];
        }
    }
    int vmax = vmin + n;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= vmax) {
            present[arr[i] - vmin] = 1;
        }
    }
    int k = 0;
    for (k = 0; k <= n; ++k) {
        if (present[k] == 0) break;
    }
    free(present);
    return vmin + k;
}


int main() {
    int arr[] = {2, 3, 5, 6, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int missing = find_missing (arr, n);
    printf ("First missing element = %d\n", missing);
    return 0;
}

Answer 3

You can use the technique of bitwise XOR.

This method has O(n) time complexity and it is working on unsorted arrays too.

Also, keep in mind, this works only if one element is missing from the array.

#include <stdio.h>

int main()
{
    int arr[] = { 1, 2, 4, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    int x = arr[0]; //XOR together all of the array elements
    for (int i = 1; i < arr_size; i++) 
    {
        x ^= arr[i];
    }
 
    int y = 1; //XOR together the numbers from 1 to size of array + 1
    for (int i = 2; i <= arr_size + 1; i++)
    {
        y ^= i;
    }
    
    int missing = x ^ y; //The missing number is going to be the XOR of the previous two.

    printf("%d", missing);

    return 0;
}