Perm-Missing-Elem: 100% functional score, but only 60% performance

Question

I cannot figure out why I didn't get 100% success from the Codility's Perm-Missing-Element test even I solve with \$O(n)\$. I will appreciate any advice/answers.

You can see the problem, my code, and the scores on the Codility site, as well as here.

Problem Definition

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:

class Solution { public int solution(int[] A); }  

that, given a zero-indexed array A, returns the value of the missing element.
For example, given array A such that:

A[0] = 2
A[1] = 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.

Solution

Here is the code I wrote as an answer:

public class Solution {

        public int solution(int[] A) {

            int N = A.length + 1;
            int total = N * (N + 1) / 2;

            for (int i : A) {

                total -= i;
            }

            return total;
        }
    }

Answer 1

@chillworld is correct in his observation that the issue is related to the int overflow causing the problems in the performance tests.

The more accurate solution to this is to use a long to set the score, instead of an int.

public class Solution {

    public int solution(int[] A) {

        long N = A.length + 1;
        long total = N * (N + 1) / 2;

        for (int i : A) {

            total -= i;
        }

        return (int)total;
    }
}

As for your code, I understand why you have variables with names like N and A, because those are the variable names used in the problem.

Those variable names do not conform to standard Java naming conventions though. They should be meaningful names, and start with a lower-case letter, like sum, and data.

the fact that my code below still uses N is not an indication that it is OK .... Do what I say, not what I do...

---

Update

Sometimes, the performance tricks in Java can be a PITA.

• Whenever you can, declare your variables as final
• declare your methods as final
• declare variables and for-loop variables as final (if you use the enhanced-for semantics).
• addition may, or may not be faster than subtraction.

Using this code:

class Solution {

    public final int solution(final int[] data) {

        final long N = data.length + 1;
        final long total = (N * (N + 1)) / 2;
        
        long sum = 0L;

        for (final int i : data) {

            sum += i;
        }

        return (int)(total - sum);
    }
}

Scores 100%

---

Update 2 final is not the issue:

public int solution(int[] data) {

    long N = data.length + 1;
    long total = (N * (N + 1)) / 2;
    
    long sum = 0L;

    for (int i : data) {

        sum += i;
    }

    return (int)(total - sum);
}

Also scores 100%

Answer 2

You could also use Java 8 IntStream API to sum the array and minimize your code:

public int solution(int[] A) {
    long N = A.length + 1;
    return (int) (((N*(N+1))/2)-IntStream.of(A).sum());
}

This will score 100%.

Answer 3

From the site :

WRONG ANSWER
got -2147483647 expected 1

So int has overflow because you count everything up. Mine solution to that problem :

public int solution(int[] A) {
    int previous = 0;
    if (A.length != 0) {
        Arrays.sort(A);
        for (int i : A) {
            if (++previous != i) {
                return previous;
            }
        }
    }
    return ++previous;
}

result see here : https://codility.com/demo/results/demoS45RNV-37J/