Given an array arr[] of N positive integers, the task is to find the number of pairs with odd sum and the number of pairs with even sum.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output:
Odd pairs = 6
Even pairs = 4
Input: arr[] = {7, 4, 3, 2}
Output:
Odd pairs = 4
Even pairs = 2
Naive Approach:
The naive approach for this problem is to go through every pair of elements in the array, check for their sums and then count the number of pairs having odd and even sum. This approach will take O(N*N) time.
Efficient Approach:
- Count the number of odd and even elements from the array and store them in variables cntEven and cntOdd.
- In order to get the pair sum as even, all the even elements will be paired with only even elements and all the odd elements will be paired with only odd elements and the count will be ((cntEven * (cntEven – 1)) / 2) + ((cntOdd * (cntOdd – 1)) / 2)
- Now, for the sum to be odd, one of the elements of the pair must be even and the other must be odd and the required count will be cntEven * cntOdd.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the count of pairs// with odd sum and the count// of pairs with even sumvoid findPairs(int arr[], int n){ // To store the count of even and // odd number from the array int cntEven = 0, cntOdd = 0; for (int i = 0; i < n; i++) { // If the current element is even if (arr[i] % 2 == 0) cntEven++; // If it is odd else cntOdd++; } // To store the count of // pairs with even sum int evenPairs = 0; // All the even elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntEven * (cntEven - 1)) / 2); // All the odd elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntOdd * (cntOdd - 1)) / 2); // To store the count of // pairs with odd sum int oddPairs = 0; // All the even elements will make pairs // with all the odd element and the // sum of the pair will be odd oddPairs += (cntEven * cntOdd); cout << "Odd pairs = " << oddPairs << endl; cout << "Even pairs = " << evenPairs;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(int); findPairs(arr, n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to find the count of pairs// with odd sum and the count// of pairs with even sumstatic void findPairs(int arr[], int n){ // To store the count of even and // odd number from the array int cntEven = 0, cntOdd = 0; for (int i = 0; i < n; i++) { // If the current element is even if (arr[i] % 2 == 0) cntEven++; // If it is odd else cntOdd++; } // To store the count of // pairs with even sum int evenPairs = 0; // All the even elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntEven * (cntEven - 1)) / 2); // All the odd elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntOdd * (cntOdd - 1)) / 2); // To store the count of // pairs with odd sum int oddPairs = 0; // All the even elements will make pairs // with all the odd element and the // sum of the pair will be odd oddPairs += (cntEven * cntOdd); System.out.println("Odd pairs = " + oddPairs); System.out.println("Even pairs = " + evenPairs);}// Driver codepublic static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; findPairs(arr, n);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to find the count of pairs # with odd sum and the count # of pairs with even sum def findPairs(arr, n) : # To store the count of even and # odd number from the array cntEven = 0; cntOdd = 0; for i in range(n) : # If the current element is even if (arr[i] % 2 == 0) : cntEven += 1; # If it is odd else : cntOdd += 1; # To store the count of # pairs with even sum evenPairs = 0; # All the even elements will make # pairs with each other and the # sum of the pair will be even evenPairs += ((cntEven * (cntEven - 1)) // 2); # All the odd elements will make # pairs with each other and the # sum of the pair will be even evenPairs += ((cntOdd * (cntOdd - 1)) // 2); # To store the count of # pairs with odd sum oddPairs = 0; # All the even elements will make pairs # with all the odd element and the # sum of the pair will be odd oddPairs += (cntEven * cntOdd); print("Odd pairs = ", oddPairs); print("Even pairs = ", evenPairs); # Driver code if __name__ == "__main__" : arr = [ 1, 2, 3, 4, 5 ]; n = len(arr); findPairs(arr, n); # This code is contributed by kanugargng |
C#
// C# implementation of the approachusing System;class GFG {// Function to find the count of pairs// with odd sum and the count// of pairs with even sumstatic void findPairs(int []arr, int n){ // To store the count of even and // odd number from the array int cntEven = 0, cntOdd = 0; for (int i = 0; i < n; i++) { // If the current element is even if (arr[i] % 2 == 0) cntEven++; // If it is odd else cntOdd++; } // To store the count of // pairs with even sum int evenPairs = 0; // All the even elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntEven * (cntEven - 1)) / 2); // All the odd elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntOdd * (cntOdd - 1)) / 2); // To store the count of // pairs with odd sum int oddPairs = 0; // All the even elements will make pairs // with all the odd element and the // sum of the pair will be odd oddPairs += (cntEven * cntOdd); Console.WriteLine("Odd pairs = " + oddPairs); Console.WriteLine("Even pairs = " + evenPairs);}// Driver codepublic static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; findPairs(arr, n);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to find the count of pairs// with odd sum and the count// of pairs with even sumfunction findPairs(arr, n) { // To store the count of even and // odd number from the array let cntEven = 0, cntOdd = 0; for (let i = 0; i < n; i++) { // If the current element is even if (arr[i] % 2 == 0) cntEven++; // If it is odd else cntOdd++; } // To store the count of // pairs with even sum let evenPairs = 0; // All the even elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntEven * (cntEven - 1)) / 2); // All the odd elements will make // pairs with each other and the // sum of the pair will be even evenPairs += ((cntOdd * (cntOdd - 1)) / 2); // To store the count of // pairs with odd sum let oddPairs = 0; // All the even elements will make pairs // with all the odd element and the // sum of the pair will be odd oddPairs += (cntEven * cntOdd); document.write("Odd pairs = " + oddPairs + "<br>"); document.write("Even pairs = " + evenPairs);}// Driver codelet arr = [1, 2, 3, 4, 5];let n = arr.length;findPairs(arr, n);// This code is contributed by _saurabh_jaiswal</script> |
Output:
Odd pairs = 6 Even pairs = 4
Complexity Analysis:
- Time Complexity : O(N).
In every iteration of for loop, an element from either of the array is processed. Therefore, the time complexity is O(N). - Auxiliary Space : O(1).
Any extra space is not required, so the space complexity is constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
