# 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 Apr 17, 2014 at 13:19
• I shared a link which just give a brief test report. They don't share a detailed report. Apr 17, 2014 at 13:23
• Ha ok, I didn't see that. So this is actually a problem of correctness and not of performance. Apr 17, 2014 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? Oct 24, 2015 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 Mar 8, 2017 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 ? Apr 17, 2014 at 13:27
• @quartaela - updated answer with 100% solution. Apr 17, 2014 at 13:37
• thanks a lot but I dont get it. How defining variables as final boost the performance from 60 to 100? Apr 17, 2014 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. Apr 17, 2014 at 13:44
• Impressive, it does not do much for my opinion of Java though :\ Apr 17, 2014 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. Apr 17, 2014 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, 2014 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. Jul 7, 2014 at 10:33
• This answer isn't correct simply because a solution bounded by N is needed. Mar 18, 2015 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. Mar 19, 2015 at 6:40