Be the first user to complete this post

Add to List 
490. Given an array, Find the number of all pairs with even sum
Objective: Given an array of integers, write a program to find the number of pairs with even sum.
Example:
Given Input: [1, 2, 3, 4] Number of even pairs: 2 Note: (1, 3) and (2, 4) Given Input: [6, 7, 1, 3, 2, 5, 4] Number of even pairs: 9
>Naive approach: Use nested loops and check the sum of each possible pair and if sum is even then add it to the result.
Time Complexity: O(N^{2})
Better approach:
 Iterate through the array and count the number of odd elements and even elements.
 We know the even + even = even and odd + odd = even, we will use this property.
 Number of pairs with even count = evenCount*(evenCount1)/2 + oddCount*(oddCount1)/2.
 NOTE: Number of ways to choose 2 elements out of n = nC2 = n*(n1)/2
Time Complexity: O(N)
Output:
Given Input: [6, 7, 1, 3, 2, 5, 4] Number of even pairs: 9