The savior? Hacker Earth Solution in C

https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/the-savior-3/description/?layout=old

 

Below is copied from editorial

Let's start with two simple math facts:

1. From elementary math we know that for any two integers a and b, a + b is even if and only if both a and b are even or both a and b are odd.
2. If you have an array of K elements, you can produce K * (K - 1) / 2 pairs of its elements

Based on these fact, we can produce an optimal solution. Let ODD be the number of odd integers in A and EVEN be the number of even integers in it.

Then the number of pairs of integers (a, b) from A for which a + b is even equals ODD * (ODD - 1) / 2 + EVEN * (EVEN - 1) / 2. We are almost there, but notice that we are interested in the number of pairs of different integers, so we are possibly counting too much here. For example, if A contains number 3 two times, then it will be taken into the result, but we do not want it to be there.

So this program will fail when there are duplicates:

#include<stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

        int a[n],i,ne=0,no=0;

        for(i=0;i<n;i++)

            scanf("%d",&a[i]);

            if(a[i]%2 == 0)

                ne++;

            else

                no++;

        }

        printf("%llu\n", (ne*(ne-1)/2)+(no*(no-1)/2));

            

    }

}

Solution:

#include<stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

        int a[n],i,j;

        unsigned long long int c=0;;

        for(i=0;i<n;i++)

            scanf("%d",&a[i]);

        for(i=0;i<n-1;i++)

            for(j=i+1;j<n;j++)

                if((a[i]+a[j])%2 == 0 && a[i] != a[j])

                    c++;    

        printf("%llu\n",c);     

    }

}