Codility PermMissingElem

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.

Try this in c#:

using System;
using System.Linq;

private static int PermMissingElem(int[] A)
    {
        if (!A.Any() || !A.Any(x => x == 1)) { return 1; }
        var size = A.Length;
        var numberTwoList = Enumerable.Range(1, size);
        var failNumber = numberTwoList.Except(A);
        if (!failNumber.Any()) { return A.Max() + 1; }
        return failNumber.FirstOrDefault();
    }

Well, when the last element is missing, you obviously return 1, since your if statement's condition is always false. Same for first element.

Take as example this input:

1 2 3 4 5

the difference will be always 1, but element 6 is missing.

The reason for this incapability of your algorithm to catch these cases, is that it examines neighboring elements (A[i + 1] and A[i]).

JS solution #1

function solution(A) {
  if (A.length === 1) {
    return A[0] > 1 ? 1 : 2;
  }
  const map = {};
  let max = 0;    
  for (let i = 0, len = A.length; i < len; i++) {
    map[A[i]] = A[i];  
    if (A[i] > max) {
        max = A[i]
    }
  }
  for (let i = 0, len = A.length; i < len; i++) {
    if (!map[i + 1]) {
      return i + 1;
    }
  }
  return max + 1
}

JS solution #2

function solution(A) {
    const s  = A.reduce((a, b) => {return a + b}, 0);
    const s2 = (A.length + 1) * (A.length + 2) / 2
    return s2 - s;
}

try this arrays (like the end test):

• [1,2,3] -> must return 4;
• [1] -> must return 2;
• [2] -> must return 1;
• [2,3] -> must return 1;
• [1, 3] -> 2

But for #2 solution [4] returns -1 and for [123] returns -120. The test will show 100 points. But actually, it doesn't work as expected on my opinion.

Both solutions work with the same performance.

Try this javascript function:

function solution(A) {
    let givenSum = 0;
    let expectedSum = 0;
    let size = A.length;
    
    for(let i = 1; i <= size +1; i++){
        expectedSum = expectedSum + i;
    }
    
    for(let i = 0; i < size; i++){
        givenSum += A[i];
    }

    return expectedSum - givenSum;
}

here is my solution: https://app.codility.com/demo/results/trainingMZWVVT-55Y/

function solution(A) {
    A = A.sort((a,b)=>a-b)
    if(A[0]!==1) return 1
    for(let i = 0; i < A.length; i++)
    {
        if(A[i+1]-A[i]!==1) return A[i] + 1
    }
    return A[A.length] + 1
}

Tested on Codility with 100% score see here The solution i implemented is using set difference. since the question guaranties exactly one element is missing.

def solution(A):
    # write your code in Python 3.6
    N = len(A)
    difference = set(range(1, N+2)) - set(A)
    return difference.pop()