Codility “PermMissingElem” Solution

Question

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.

Answer 1

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.

Answer 2

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.