Given an array, find the number of all pairs with odd sum.

Objective: Given an array of integers, write a program to find the number of pairs with even odd.


Given Input: [1, 2, 3, 4]
Number of odd pairs: 4
Note: (1, 2), (1, 4), (2, 3) and (3, 4)

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

Naive approach: Use nested loops and check the sum of each possible pair and if the sum is odd then add it to the result.

Time Complexity: O(N2)

Better approach:

  1. Iterate through the array and count the number of odd elements and even elements.
  2. We know the odd + even = odd, we will use this property.
  3. Number of pairs with odd count = evenCount*oddCount.

Time Complexity: O(N)

Complete Code:


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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: