Given an array arr[], the task is to count pairs such that each pair (arr[i], arr[j]) contains at least one even element in it where i != j.
Examples:
Input: arr[] = {1, 2, 3, 1, 3}
Output: 4
Explanation:
Possible pairs are: (1, 2), (2, 3), (2, 1), (2, 3).Input: arr[] = {8, 2, 3, 1, 4, 2}
Output: 14
Explanation:
Possible pairs are: (8, 2), (8, 3), (8, 1), (8, 4), (8, 2), (2, 3), (2, 1), (2, 4), (2, 2), (3, 4), (3, 2), (1, 4), (1, 2), (4, 2).
A Simple Approach is to run two loops. Pick each element one-by-one and for each element find element on right side of array that holds condition, then increment count.
Time Complexity:
Below is the implementation of the above approach:
C++
// C++ implementation to count // pairs in an array such that // each pair contains at // least one even element #include<bits/stdc++.h> using namespace std; // Function to count the pairs in // the array such as there is at // least one even element in each pair int CountPairs(int arr[], int n) { int count = 0; // Generate all possible pairs // and increment then count // if the condition is satisfied for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if (arr[i] % 2 == 0 || arr[j] % 2 == 0) count++; } } return count; } // Driver code int main() { int arr[] = { 8, 2, 3, 1, 4, 2 }; int n = sizeof(arr) / sizeof(int); // Function call cout << (CountPairs(arr, n)); } // This code is contributed by rock_cool |
Java
// Java implementation to Count// pairs in an array such that// each pair contains at// least one even elementimport java.util.*;class GFG { // Function to count the pairs in // the array such as there is at // least one even element in each pair static int CountPairs(int[] arr, int n) { int count = 0; // Generate all possible pairs // and increment then count // if the condition is satisfied for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] % 2 == 0 || arr[j] % 2 == 0) count++; } } return count; } // Driver code public static void main(String[] args) { int[] arr = { 8, 2, 3, 1, 4, 2 }; int n = arr.length; // Function Call System.out.println(CountPairs(arr, n)); }} |
Python3
# Python3 implementation to count # pairs in an array such that # each pair contains at # least one even element def CountPairs(arr, n): count = 0 # Generate all possible pairs # and increment then count # if the condition is satisfied for i in range(n): for j in range(i + 1, n): if (arr[i] % 2 == 0 or arr[j] % 2 == 0): count += 1 return count # Driver code arr = [ 8, 2, 3, 1, 4, 2 ]n = len(arr)# Function callprint(CountPairs(arr, n))# This code is contributed by rutvik_56 |
C#
// C# implementation to count // pairs in an array such that // each pair contains at // least one even element using System; class GFG{ // Function to count the pairs in // the array such as there is at // least one even element in each pair static int CountPairs(int[] arr, int n) { int count = 0; // Generate all possible pairs // and increment then count // if the condition is satisfied for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if (arr[i] % 2 == 0 || arr[j] % 2 == 0) count++; } } return count; } // Driver code public static void Main(String[] args) { int[] arr = { 8, 2, 3, 1, 4, 2 }; int n = arr.Length; // Function Call Console.WriteLine(CountPairs(arr, n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation to count// pairs in an array such that each // pair contains at least one even element// Function to count the pairs in// the array such as there is at// least one even element in each pairfunction CountPairs(arr, n){ let count = 0; // Generate all possible pairs // and increment then count // if the condition is satisfied for(let i = 0; i < n; i++) { for(let j = i + 1; j < n; j++) { if (arr[i] % 2 == 0 || arr[j] % 2 == 0) count++; } } return count;}// Driver codelet arr = [ 8, 2, 3, 1, 4, 2 ];let n = arr.length;// Function calldocument.write(CountPairs(arr, n));// This code is contributed by divyeshrabadiya07</script> |
Output:
14
Efficient Approach: The idea is to count the even and odd elements in the array and include pairs having only one even element or both the pairs to be even element.
- Pair having exactly one even element: count of the pairs having exactly one even element will be:
- Pair having exactly two even elements: count of the pairs having exactly two even elements will be:
Therefore, the count of the pairs having at least one even element will be 
Below is the implementation of the above approach:
C++
// C++ implementation to Count// pairs in an array such that// each pair contains at// least one even element#include <bits/stdc++.h> using namespace std;// Function to count the pairs in// the array such as there is at// least one even element in each pairint CountPairs(int arr[], int n){ // Store count of even // and odd elements int even = 0, odd = 0; for(int i = 0; i < n; i++) { // Check element is // even or odd if (arr[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (even * odd);}// Driver Codeint main(){ int arr[] = { 8, 2, 3, 1, 4, 2 }; int n = sizeof(arr) / sizeof(int); cout << CountPairs(arr, n);}// This code is contributed by jrishabh99 |
Java
// Java implementation to Count// pairs in an array such that// each pair contains at// least one even elementimport java.util.*;class GFG { // Function to count the pairs in // the array such as there is at // least one even element in each pair static int CountPairs(int[] arr, int n) { // store count of even // and odd elements int even = 0, odd = 0; for (int i = 0; i < n; i++) { // check element is // even or odd if (arr[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (even * odd); } // Driver Code public static void main(String[] args) { int[] arr = { 8, 2, 3, 1, 4, 2 }; int n = arr.length; System.out.println(CountPairs(arr, n)); }} |
Python3
# Python3 implementation to count # pairs in an array such that # each pair contains at # least one even element # Function to count the pairs in # the array such as there is at # least one even element in each pair def CountPairs(arr, n): # Store count of even # and odd elements even = 0 odd = 0 for i in range(n): # Check element is # even or odd if (arr[i] % 2 == 0): even += 1 else: odd += 1 return ((even * (even - 1)) // 2 + (even * odd)) # Driver Code arr = [ 8, 2, 3, 1, 4, 2 ] n = len(arr) print(CountPairs(arr, n)) # This code is contributed by code_hunt |
C#
// C# implementation to Count // pairs in an array such that // each pair contains at // least one even element using System; class GFG{ // Function to count the pairs in // the array such as there is at // least one even element in each pair static int CountPairs(int[] arr, int n) { // Store count of even // and odd elements int even = 0, odd = 0; for(int i = 0; i < n; i++) { // Check element is // even or odd if (arr[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (even * odd); } // Driver Code public static void Main() { int[] arr = { 8, 2, 3, 1, 4, 2 }; int n = arr.Length; Console.Write(CountPairs(arr, n)); } } // This code is contributed by Nidhi_biet |
Javascript
<script> // Javascript implementation to Count // pairs in an array such that // each pair contains at // least one even element // Function to count the pairs in // the array such as there is at // least one even element in each pair function CountPairs(arr, n) { // Store count of even // and odd elements let even = 0, odd = 0; for(let i = 0; i < n; i++) { // Check element is // even or odd if (arr[i] % 2 == 0) even++; else odd++; } return (even * (even - 1)) / 2 + (even * odd); } let arr = [ 8, 2, 3, 1, 4, 2 ]; let n = arr.length; document.write(CountPairs(arr, n)); // This code is contributed by divyesh072019.</script> |
Output:
14
Time Complexity: O(N)
Space Complexity: O(1)
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!
