Problem

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

    int solution(int A[], int N);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

    •         N is an integer within the range [0..100,000];
    •         the elements of A are all distinct;
    •         each element of array A is an integer within the range [1..(N + 1)].

Note:

The values in the array start from 1 to N + 1. They are simply not arranged in ascending order. In the illustration array, of the problem, there are 4 elements, and when arranged in ascending order, they become 1, 2, 3, 5. It can clearly be seen from this ascending order, that 4 is missing. The 4 happens to be missing at the end of the list.

It can be very cumbersome to solve this problem, the brute-force (direct) way. The best way to do it is to sort the array (vector), and then scan it for the missing element. This will give O(Nxlog(N)) time complexity at app.codility.com/programmers .

Solution

app.codility.com/programmers allows the candidate to use the predefined qsort() function in C. It is in the stdlib library, which has to be included. The following program offers the solution (read the code and comments):

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

    int compFn(const void *a, const void *b) {
        int int_a = *((int *)a);
        int int_b = *((int *)b);
        return int_a - int_b;
    }

    //sort using C sort, then look for the missing element from the beginning
    int solution(int A[], int N) {

        qsort(A, N, sizeof(int), compFn);  //sort function from the algorithm library

        int ctr = 1;  //counter
        for (int i=0; i<N; i++){
            if (ctr != A[i])    //A[0] should be 1
                return ctr;    //missing element
            ++ctr;
        }

        return ctr;   //element is missed at end of list
    }

    int main() 
    {  
        int B[] = {2, 3, 1, 5};
        int N = sizeof(B) / sizeof(B[0]);    //divide size of array by size of one (first) element
        int miss = solution(B, N);
        printf("%i\n", miss);

        return 0; 
    } 

The qsort function is a predefined function in the C standard library (actually the stdlib sub library). It needs a compare function (compFn() in this case) that compares two numbers. The compare function, receives as arguments, two memory addresses, 'a' and b. In the compare function, (int *)a for example, means, put the address as value into a pointer object (variable). *((int *)a) means, return the value pointed to, by the pointer object (int *)a.

What matters with the compare function is, that a positive value is returned, or zero is returned or a negative value is returned.

It is the predefined qsort() function that calls the user defined compFn() function, by sending it two references (addresses); and the programmer (developer) should not border about the definition of the references. The last argument of the qsort function call, is the user defined compare function, compFn without the parentheses.

The output is 4, as expected. Read through the code if that is not already done.

The value of ctr is incremented at the end of the for-loop's body. It is synchronized with the sorted elements. In the for-loop scan, when it is not equal to a sorted element, then its value is the missing element; otherwise the element is missed at the end of list.

The example test has been used here. On submission at app.codility.com/programmers, at least 8 test cases not shown here will assess your solution. Remember that at app.codility.com/programmers, the C main() function is not submitted.

Conclusion

To solve a similar problem, efficiently, sort the array, and then scan for the missing element.

The reader should register at app.codility.com/programmers and be testing his/her code, in order to gain confidence.