**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
and*even + even = even*, we will use this property.*odd + odd = even* - Number of pairs with even count = evenCount*(evenCount-1)/2 + oddCount*(oddCount-1)/2.
**NOTE:**Number of ways to choose 2 elements out of n = nC2 = n*(n-1)/2

Time Complexity: O(N)

**Complete Code:**

**Output:**

Given Input: [6, 7, 1, 3, 2, 5, 4] Number of even pairs: 9