Monthly Archives: August 2014

Simple things matter

Today, out of boring, I did visit again codility to take a few tests. Their free tests aren’t much of a challenge, so I got them one by one, each in 5 minutes or so. Then I come across a test which, to my opinion, just a little trick question:

Problem: PermMissingElem

Task description
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.

Feel free to drop a few minutes to think it through. It isn’t even hard.

You finished your program? Ok, then let’s continue.
I took my 5 minutes and write a very simple script, including the unit tests:

First Solution
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int sum = 0;
int sumTotal = (A.length + 1) * (A.length + 2) / 2;

for (int i = 0; i < A.length; i++) {
sum = sum + A[i];
}

int result = sumTotal - sum;
return result;
}
}

Unit tests:

  • [6,5,4,3,2]
  • [2, 5, 1, 4]
  • [2]
  • [1]
  • [6,3,5,4,2,1]


All my unit tests passed. I submitted, kind of waiting for another 100%. But it was FAILED with n ~ 1,000,000.

My algorithm is right, I know that. So what’s the matter with big number?

In case you’re still wonder, here’s the program that worked and got 100% score:

Right Solution

class Solution
public int solution(int[] A) {
// write your code in Java SE 8
int sum = 0;
int sumTotal = 0;

for (int i = 0; i < A.length; i++) {
sum = sum + A[i];
}

for (int i = 1; i <= A.length + 1; i++) {
sumTotal = sumTotal + i;
}

int result = sumTotal - sum;
return result;
}
}

Can you tell the difference? :)