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:
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:
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:
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?