3
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Have you looked at this related question? \$\endgroup\$
    – yuri
    Jun 7, 2017 at 20:26
  • \$\begingroup\$ Can you share a performance test which reveals \$O(N\log{N})\$ complexity? \$\endgroup\$
    – vnp
    Jun 8, 2017 at 1:52
  • \$\begingroup\$ 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. \$\endgroup\$
    – James Ray
    Feb 28, 2019 at 5:25

2 Answers 2

3
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.