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

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 = 2
A = 3
A = 1
A = 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;
}

}
}

• Doesn't codility provide you more details about this ? Type of test cases for instance – SylvainD Apr 17 '14 at 13:19
• I shared a link which just give a brief test report. They don't share a detailed report. – quartaela Apr 17 '14 at 13:23
• Ha ok, I didn't see that. So this is actually a problem of correctness and not of performance. – SylvainD Apr 17 '14 at 13:44
• I'm confused. Where are people getting the formula for Total? Obviously the result is the sum of all array elements plus the missing element, because that's how we're treating it to get the right answer. But how do we arrive at that formula? – KairisCharm Oct 24 '15 at 16:19
• @KairisCharm it's the arithmetic progression formula. Everybody discusses the easy part (implementing) and give math for granted which is the most challenging for reaching the solution. This tests are not testing for software engineering they're testing algebra en.wikipedia.org/wiki/Arithmetic_progression – Sebastian Sastre Mar 8 '17 at 12:36

@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%

• believe me I tried that solution which gives the same result :). But variable names doesnt affect performance right ? – quartaela Apr 17 '14 at 13:27
• @quartaela - updated answer with 100% solution. – rolfl Apr 17 '14 at 13:37
• thanks a lot but I dont get it. How defining variables as final boost the performance from 60 to 100? – quartaela Apr 17 '14 at 13:41
• @quartaela - I am pretty convinced your code would have passed with just the long-based arithmetic.... the performance tests were failing, they were not slow. The code above just gives a solution that works in all situations, not just smaller datasets. I will put another test through with the same code, but different final, and see what happens. – rolfl Apr 17 '14 at 13:44
• Impressive, it does not do much for my opinion of Java though :\ – konijn Apr 17 '14 at 13:45

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%.

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/

• Arrays.sort is typically an O(n log n) operation, so it will likely fail the scalability test. – rolfl Apr 17 '14 at 13:23
• Did I miss something in the requirements? When I sent an input of int[] A = {26,23,21,24,22};, I did not get the desired result using your method. It could be that I am missing something in the requirement, so please clarify. – user47764 Jul 7 '14 at 3:41
• @KayAshton This won't work cause the pre requirement is that you start at 1 (or 2 if 1 is missing). Also you can't have an exact result when you have int[] A = {25,23,21,24,22}; because it could be 20 or 26. – chillworld Jul 7 '14 at 10:33
• This answer isn't correct simply because a solution bounded by N is needed. – Christo Mar 18 '15 at 20:22
• @CodingChief There is a difference between not correct and not optimized. The code works for every case, but indeed rolfl his code is more optimized, and that is also the reason that his answer is accepted as correct one. – chillworld Mar 19 '15 at 6:40