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(vector<int> &A);

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 sort() function in C++. It is in the algorithm library, which has to be included. The following program offers the solution (read the code and comments):

    #include <iostream> 
    #include <vector>
    #include <algorithm>
    using namespace std; 

    //sort using C++ sort, then look for the missing element from the beginning
    int solution(vector<int> &A) {
        int N = A.size();

        sort(A.begin(), A.end());  //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() 
    {  
        vector<int> B{2, 3, 1, 5};
        int miss = solution(B);
        cout << miss << endl;

        return 0; 
    } 

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 or vector, 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.