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.

Example:

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:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

GoogleMicrosoftAmazonFacebookmore..

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: