review of a codility test - pair_sum_even_count

Question

I recently took an online test on codility as part of a recruitment process. I was given two simple problems to solve in 1 hour. For those who don't know codility, its an online coding test site where you can solve ACM style problems in many different languages.

If you have 30 or so mins then check this http://codility.com/demo/run/

My weapon of choice is usually Java.

So, one of the problems I have is as follows (I will try to remember, should have taken a screenshot)

Lets say you have array A[0]=1 A[1]=-1 ....A[n]=x

Then what would be the smartest way to find out the number of times when A[i]+A[j] is even where i < j

So if we have {1,2,3,4,5} we have 1+3 1+5 2+4 3+5 = 4 pairs which are even

The code I wrote was some thing along the lines

int sum=0;
for(int i=0;i<A.length-1;i++){
 for (int j=i+1;j<A.length;j++){
   if( ((A[i]+A[j])%2) == 0 && i<j) {
       sum++;
    }
  }
}

There was one more restriction that if the number of pairs is greater than 1e9 then it should retrun -1, but lets forget it.

Can you suggest a better solution for this. The number of elements won't exceed 1e9 in normal cases.

I think I got 27 points deducted for the above code (ie it's not perfect). Codility gives out a detailed assessment of what went wrong, I don't have that right now.

Answer 1

The sum of two integers is even if and only if they are either both even or both odd. You can simply go through the array and count evens and odds. The number of possibilities to combine k numbers from a set of size N is N! / ((N - k)! · k!). You just need to put the number of evens/odds as N and 2 as k. For this, the above simplifies to (N · (N - 1)) / 2. All the condition i < j does is to specify that each combination counts only once.

Answer 2

It's very simple First you need to find the number of odds and even number in collection. eg. x is odd if x&1 ==1, even otherwise, if you have this, knowing that adding two even or two odds to each you get even. You need to calc the sum of Combinations of two elements from Even numbers and Odd numbers.

having int A[] = {1,2,3,4,5};

int odds=0, evens=0;
for (int i=0; i< A.length; ++i)
{
if (A[i]&1==1) odds++;
else evens++;
}
return odds*(odds-1)/2 + evens*(evens-1)/2;  

// Above goes from fact that the number of possibilities to combine k numbers from a set of size N is N! / ((N - k)! · k!). For k=2 this simplifies to (N · (N - 1)) / 2