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:

    function solution(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.

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, 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 JavaScript. The array has this sort() method. The following program offers the solution (read the code and comments):

<script type='text/javascript'>
    "use strict"; 

    //sort using JavaScript array sort, then look for the missing element from the beginning
    function solution(A) {
        let N = A.length;

        A.sort();  //sort method from the array data structure

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

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

    let B = [2, 3, 1, 5];
    let miss = solution(B);
    document.write(miss);
</script>

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 JavaScript calling 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.