# Codility “PermMissingElem” Solution

This is my solution to the PermMissingElem problem, I wonder what can be improved? Expected worst case time complexity is O(N), but the performance test shows that it's O(N) or O(N * log(N)), which I suppose there's some solution out there that can truly achieve pure O(N)?

function solution(A) {
const size = A.length;
let sum = 0;

for (i=0;i<size;i++){
sum += A[i];
}

return (((size+ 1)*(size + 2))/2) - sum
}


The original problem is quoted as follows:

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.

Write a function:

int solution(int A[], int N); that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2 A1 = 3 A[2] = 1 A[3] = 5 the function should return 4, as it is the missing element.

Assume that:

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)].

Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

• Have you looked at this related question?
– yuri
Jun 7, 2017 at 20:26
• Can you share a performance test which reveals $O(N\log{N})$ complexity?
– vnp
Jun 8, 2017 at 1:52
• Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array. Feb 28, 2019 at 5:25

With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:

1. Within a function, it is better to declare your variables using the var keyword. You should apply this to the i inside for() loop
2. The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
3. You can choose better variables and function names.

A minor modification:

function solution(A) {
const size = A.length;
let sum = 0;

for (let int of A){
sum += int;
}

return (((size + 1)*(size + 2))/2) - sum
}


Note that I've kept the function name because it is what the exercises/tests in Codility use.

As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $$\O(n)\$$ or $$\O(N\log{N})\$$ are acceptable time complexities. The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $$\O(N\log{N})\$$ time complexity. So both of our solutions are $$\O(n)\$$ complexity.