Search code examples
algorithmfunction

Codility PermMissingElem

My solution scored only 40% correctness on Codility.

What am I doing wrong?

Here is the test result (https://codility.com/demo/results/trainingU7KSSG-YNX/)

Problem:

A zero-indexed 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.

Solution:

function solution(A) {
    var output = 1;
    var arrayLength = A.length;

    if(!arrayLength){
        return output;
    }

    if(arrayLength == 1) {
        return A[0] + 1;
    }    

   var sorted = A.sort(sortingFn);        

    for(var i = 0; i < A.length - 1; i++) {
        if(A[i+1] - A[i] > 1) {
            output =  A[i] + 1;            
            break;
        } 
    }

    return output;
}

function sortingFn(a, b) {
    return a - b;
}

Result

enter image description here

Solution

  • Your algorithm find the missing element by comparing neighboring elements in the array. This means it is incapable of handling cases where the first or last element is missing, as these only have a single neighbor.

    Consider as an example [1, 2, 3]. The missing element would be 4. But since 4 has precisely one neighbor (3), it can't be found by the algorithm, and 1 will be returned.

    In addition your algorithm is rather inefficient, as sorting takes O(n lg n), while the problem is solveable in O(n):

    find_missing(arr):
    s  = sum(arr)
    s' = (len(arr) + 1) * (len(arr) + 2) / 2

    return s' - s

    This code works by summing up all elements in the array and comparing it to expected sum, if all elements were present. The advantage of this approach is that it only requires linear operations and will find the missing element with relative simplicity.