Given an array A[] of integers, the task is to find the total number of pairs such that each pair contains either both even or both odd elements. A valid pair (A[ i ], A[ j ]) can only be formed if i != j.
Examples:
Input: A[ ] = {1, 2, 3, 1, 3}
Output: 6
Explanation:
Possible odd pairs = (1, 3), (1, 1), (1, 3), (3, 1), (3, 3), (1, 3) = 6
Possible even pairs = 0
Hence, total pairs = 6 + 0 = 6Input: A[ ] = {8, 2, 3, 1, 4, 2}
Output: 7
Explanation:
Possible odd pair = (3, 1) = 1
Possible even pairs = (8, 2), (8, 4), (8, 2), (2, 4), (2, 2), (4, 2) = 6
Hence, total pairs = 6 + 1 = 7
Naive Approach:
The simplest approach is to generate all possible pairs. For each pair, check if both elements are odd or both are even. If so, increment a counter. The final count will be the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the answerint countPairs(int A[], int n){ int count = 0, i, j; // Generate all possible pairs for(i = 0; i < n; i++) { for(j = i + 1; j < n; j++) { // Increment the count if // both even or both odd if ((A[i] % 2 == 0 && A[j] % 2 == 0) || (A[i] % 2 != 0 && A[j] % 2 != 0)) count++; } } return count;}// Driver Codeint main(){ int A[] = { 1, 2, 3, 1, 3 }; int n = sizeof(A) / sizeof(int); cout << countPairs(A, n);}// This code is contributed by jrishabh99 |
Java
// Java program for above approachimport java.util.*;class GFG { static int countPairs( int[] A, int n) { int count = 0, i, j; // Generate all possible pairs for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Increment the count if // both even or both odd if ((A[i] % 2 == 0 && A[j] % 2 == 0) || (A[i] % 2 != 0 && A[j] % 2 != 0)) count++; } } return count; } // Driver Code public static void main( String[] args) { int[] A = { 1, 2, 3, 1, 3 }; int n = A.length; System.out.println( countPairs(A, n)); }} |
Python3
# Python3 program for # the above approach# Function to return the answerdef countPairs(A, n): count = 0 # Generate all possible pairs for i in range (n): for j in range (i + 1, n): # Increment the count if # both even or both odd if ((A[i] % 2 == 0 and A[j] % 2 == 0) or (A[i] % 2 != 0 and A[j] % 2 != 0)): count += 1 return count# Driver Codeif __name__ == "__main__": A = [1, 2, 3, 1, 3] n = len(A) print(countPairs(A, n)) # This code is contributed by Chitranayal |
C#
// C# program for above approach using System; class GFG{ static int countPairs(int[] A, int n) { int count = 0, i, j; // Generate all possible pairs for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Increment the count if // both even or both odd if ((A[i] % 2 == 0 && A[j] % 2 == 0) || (A[i] % 2 != 0 && A[j] % 2 != 0)) count++; } } return count; } // Driver Code public static void Main(String[] args) { int[] A = { 1, 2, 3, 1, 3 }; int n = A.Length; Console.Write(countPairs(A, n)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script>// Javascript program for above approachfunction countPairs(A, n){ let count = 0, i, j; // Generate all possible pairs for(i = 0; i < n; i++) { for(j = i + 1; j < n; j++) { // Increment the count if // both even or both odd if ((A[i] % 2 == 0 && A[j] % 2 == 0) || (A[i] % 2 != 0 && A[j] % 2 != 0)) count++; } } return count;}// Driver code let A = [ 1, 2, 3, 1, 3 ];let n = A.length;document.write(countPairs(A, n));// This code is contributed by rameshtravel07</script> |
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
Traverse the array and count and store even and odd numbers in the array and calculate the possible pairs from respective counts and display their sum.
Let the count of even and odd elements in the array be EC and OC respectively.
Count of even pairs = ( EC * ( EC – 1 ) ) / 2
Count of odd pairs = ( OC * ( OC – 1 ) ) / 2
Hence, total number of possible pairs = (( EC * ( EC – 1 ) ) + ( OC * ( OC – 1 ) ))/ 2
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int countPairs(int A[], int n){ // Store count of // even and odd elements int even = 0, odd = 0; for(int i = 0; i < n; i++) { if (A[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;}// Driver codeint main(){ int A[] = { 1, 2, 3, 1, 3 }; int n = sizeof(A) / sizeof(int); cout << countPairs(A, n);}// This code is contributed by jrishabh99 |
Java
// Java program for the above approachimport java.util.*;class GFG { static int countPairs( int[] A, int n) { // Store count of // even and odd elements int even = 0, odd = 0; for (int i = 0; i < n; i++) { if (A[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; } // Driver Program public static void main( String[] args) { int[] A = { 1, 2, 3, 1, 3 }; int n = A.length; System.out.println( countPairs(A, n)); }} |
Python3
# Python3 program for the above approach # Function to return count of pairsdef countPairs(A, n): # Store count of # even and odd elements even, odd = 0, 0 for i in range(0, n): if A[i] % 2 == 0: even = even + 1 else: odd = odd + 1 return ((even * (even - 1)) // 2 + (odd * (odd - 1)) // 2)# Driver codeA = [ 1, 2, 3, 1, 3 ]n = len(A)print(countPairs(A, n)) # This code is contributed by jrishabh99 |
C#
// C# program for the above approach using System; class GFG{ static int countPairs(int[] A, int n) { // Store count of // even and odd elements int even = 0, odd = 0; for(int i = 0; i < n; i++) { if (A[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; } // Driver code public static void Main() { int[] A = { 1, 2, 3, 1, 3 }; int n = A.Length; Console.Write(countPairs(A, n)); } } // This code is contributed by nidhi_biet |
Javascript
<script> // Javascript program for the above approach function countPairs(A, n) { // Store count of // even and odd elements let even = 0, odd = 0; for(let i = 0; i < n; i++) { if (A[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; } let A = [ 1, 2, 3, 1, 3 ]; let n = A.length; document.write(countPairs(A, n)); </script> |
6
Time complexity: O(N)
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
