review of a codility test - pair_sum_even_count

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 mor开发者_如何学Ce 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.

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.

You can find the sum without calculating every pair individually.

A[i]+A[j] is even if A[i] is even and A[j] is even; or A[i] is odd and A[j] is odd.

A running total of odd and even numbers up to j can be kept, and added to sum depending on whether A[j] is odd or even:

int sum = 0;

int odd = 0;
int even = 0;
for(int j = 0; j < A.length; j++) {
    if(A[j] % 2 == 0) {
        sum += even;
        even++;
    } else {
        sum += odd;
        odd++;
    }
}

Edit:

If you look at A={1,2,3,4,5}, each value of j would add the number of pairs with A[j] as the second number.

Even values:
A[j]=2 - sum += 0
A[j]=4 - sum += 1 - [2+4]

Odd values:
A[j]=1 - sum += 0
A[j]=3 - sum += 1 - [1+3]
A[j]=5 - sum += 2 - [1+5, 3+5]

Please check this

if (A == null || A.length < 2) {
  return 0;
}

int evenNumbersCount = 0;
int oddNumberCount = 0;

for (int aA : A) {
  if (aA % 2 == 0) {
    evenNumbersCount++;
  } else {
    oddNumberCount++;
  }
}

int i = (evenNumbersCount * (evenNumbersCount - 1)) / 2 + (oddNumberCount * (oddNumberCount - 1)) / 2;
return i > 1000000000 ? -1 : i;

If someone has a problem with understanding what Sante said here is another explanation: Only odd+odd and even+even gives even. You have to find how many even and odd numbers are there. When you have it imagine that this as a problem with a meeting. How many people distinkt pairs are in the odd numbers list and even numbers list. This is the same problem as how many pairs will say hallo to each other at the party. This is also the number of edges in full graph. The answer is n*(n-1)/2 because there are n people, and you have to shake n-1 peoples hands and divide by 2 because the other person cant count your shake as distinct one. As you have here two separate "parties" going on you have to count them independently.

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

See this answer also

int returnNumOFOddEvenSum(int [] A){
    int sumOdd=0;
    int sumEven=0;

    if(A.length==0)
        return 0;

    for(int i=0; i<A.length; i++)
    {
        if(A[i]%2==0)
            sumEven++;
        else
            sumOdd++;
    }
    return factSum(sumEven)+factSum(sumOdd);
}

int factSum(int num){
    int sum=0;
    for(int i=1; i<=num-1; i++)
    {
        sum+=i;
    }
    return sum;
}

public int getEvenSumPairs(int[] array){

    int even=0;
    int odd=0;
    int evenSum=0;

     for(int j=0; j<array.length; ++j){

           if(array[j]%2==0) even++;
           else odd++;
     }
     evenSum=((even*(even-1)/2) + (odd *(odd-1)/2) ;
     return evenSum;
}

A Java implementation that works great based on the answer by "Svante":

int getNumSumsOfTwoEven(int[] a) {

    long numOdd = 0;
    long numEven = 0;
    for(int i = 0; i < a.length; i++) {
        if(a[i] % 2 == 0) { //even
            numOdd++;
        } else {
            numEven++;
        }
    }

    //N! / ((N - k)! · k!), where N = num. even nums or num odd nums, k = 2
    long numSumOfTwoEven = (long)(fact(numOdd) / (fact(numOdd - 2) * 2));
    numSumOfTwoEven += (long)(fact(numEven) / (fact(numEven - 2) * 2));

    if(numSumOfTwoEven > ((long)1e9)) {
        return -1;
    }
    return numSumOfTwoEven;

}
// This is a recursive function to calculate factorials
long fact(int i) {
    if(i == 0) {
        return 1;
    }
    return i * fact(i-1);
}

Algorithms are boring, here is a python solution.

>>> A = range(5)
>>> A
[0, 1, 2, 3, 4]
>>> even = lambda n: n % 2 == 0
>>> [(i, j) for i in A for j in A[i+1:] if even(i+j)]
[(0, 2), (0, 4), (1, 3), (2, 4)]

I will attempt another solution using vim.

You can get rid of the if/else statement and just have the following:

int pair_sum_v2( int A[], int N ) {
int totals[2] = { 0, 0 };

for (int i = 0; i < N; i++ ) {
    totals[ A[i] & 0x01 ]++;
    }

return ( totals[0] * (totals[0]-1) + totals[1] * (totals[1]-1) ) / 2;
}

Let count odd numbers as n1 and count even numbers as n2.

The sum of Pair(x,y) is even, only if we choose both x and y from the set of even numbers or both x and y from odd set (selecting x from even set and y from odd set or vice-versa will always result in the pair's sum to be an odd number).

So total combination such that each pair's sum is even = n1C2 + n2C2.

= (n1!) / ((n1-2)! * 2!) + (n2!) / ((n2-2)! * 2!)  
= (n1 * (n1 - 1)) / 2 + (n2 * (n2 - 1)) / 2 

--- Equation 1.
e.g : let the array be like: {1,2,3,4,5}
number of even numbers = n1 = 2
number of odd numbers = n2 = 2

Total pair such that the pair's sum is even from equation: 1 = (2*1)/2 + (3*2)/2 = 4 and the pairs are: (1,3), (1,5), (2,4), (3,5).
Going by traditional approach of adding and then checking might result in an integer overflow in programming on both positive as well as on negative extremes.

This is some pythonic solution

x = [1,3,56,4,3,2,0,6,78,90]

def solution(x):
    sumadjacent = [x[i]+x[i+1] for i in range(len(x)-1) if x[i] < x[i+1]]
    evenpairslist = [ True for j in sumadjacent if j%2==0]
    return evenpairslist

if __name__=="__main__":
    result=solution(x)
    print(len(result))

    int total = 0;
    int size = A.length;
    for(int i=0; i < size; i++) {
        total += (A[size-1] - A[i]) / 2;
    }
    System.out.println("Total : " + total);