Given an array of n positive numbers, the task is to count number of ordered pairs with even and odd product. Ordered pairs means (a, b) and (b,a) will be considered as different.
Examples:
Input: n = 3, arr[] = {1, 2, 7}
Output: Even product Pairs = 4, Odd product Pairs = 2
The ordered pairs are (1, 2), (1, 7), (2, 1), (7, 1), (2, 7), (7, 2)
Pairs with Odd product: (1, 7), (7, 1)
Pairs with Even product: (1, 2), (2, 7), (2, 1), (7, 2)Input: n = 6, arr[] = {2, 4, 5, 9, 1, 8}
Output: Even product Pairs = 24, Odd product Pairs = 6
Brute Force Approach:
A brute force approach to solve this problem would be to consider all possible pairs of numbers (a, b) from the given array and check whether their product is even or odd. If it is even, increment the count of even product pairs and if it is odd, increment the count of odd product pairs. Since we need to consider all possible pairs.
Below is implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to count the number of ordered pairs with even and odd productvoid countProductPairs(int arr[], int n, int& evenPairs, int& oddPairs){ for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ if(arr[i]*arr[j] % 2 == 0){ evenPairs++; } else { oddPairs++; } } }}// Driver codeint main(){ int n = 3; int a[] = { 1, 2, 7 }; int evenPairs = 0, oddPairs = 0; countProductPairs(a, n, evenPairs, oddPairs); cout << "Even Product Pairs = " << evenPairs * 2 << endl; cout << "Odd Product Pairs = " << oddPairs * 2 << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to count the number of ordered pairs with even and odd product static void countProductPairs(int[] arr, int n, int[] pairs) { int evenPairs = 0; int oddPairs = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] * arr[j] % 2 == 0) { evenPairs++; } else { oddPairs++; } } } pairs[0] = evenPairs * 2; pairs[1] = oddPairs * 2; } // Driver code public static void main(String[] args) { int n = 3; int[] arr = {1, 2, 7}; int[] pairs = new int[2]; countProductPairs(arr, n, pairs); System.out.println("Even Product Pairs = " + pairs[0] ); System.out.println("Odd Product Pairs = " + pairs[1]); }} |
Python3
# Function to count the number of ordered pairs with even and odd productdef countProductPairs(arr, n): evenPairs = 0 oddPairs = 0 for i in range(n): for j in range(i+1, n): if arr[i]*arr[j] % 2 == 0: evenPairs += 1 else: oddPairs += 1 return (evenPairs, oddPairs)# Driver coden = 3a = [1, 2, 7]evenPairs, oddPairs = countProductPairs(a, n)print("Even Product Pairs = ", evenPairs * 2)print("Odd Product Pairs = ", oddPairs * 2) |
C#
using System;public class Program { // Function to count the number of ordered pairs with // even and odd product static void CountProductPairs(int[] arr, int n, out int evenPairs, out int oddPairs) { evenPairs = 0; oddPairs = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((arr[i] * arr[j]) % 2 == 0) { evenPairs++; } else { oddPairs++; } } } } // Driver code static void Main(string[] args) { int n = 3; int[] a = { 1, 2, 7 }; int evenPairs, oddPairs; CountProductPairs(a, n, out evenPairs, out oddPairs); Console.WriteLine("Even Product Pairs = " + (evenPairs * 2)); Console.WriteLine("Odd Product Pairs = " + (oddPairs * 2)); }}// This code is contributed by user_dtewbxkn77n |
Javascript
// Function to count the number of ordered pairs with even and odd productfunction countProductPairs(arr, n, evenPairs, oddPairs) { for(let i=0; i<n; i++){ for(let j=i+1; j<n; j++){ if(arr[i]*arr[j] % 2 == 0){ evenPairs++; } else { oddPairs++; } } }}// Driver codelet n = 3;let a = [ 1, 2, 7 ];let evenPairs = 0, oddPairs = 0;countProductPairs(a, n, evenPairs, oddPairs);console.log("Even Product Pairs = " + evenPairs * 2);console.log("Odd Product Pairs = " + oddPairs * 2); |
Output
Even Product Pairs = 4 Odd Product Pairs = 2
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Approach:
The product of two numbers is odd only if both are numbers are odd. Therefore:
Number of odd product pairs = (count of odd numbers) * (count of odd numbers – 1)
And the number of even product pairs will be an inversion of number of odd product pairs. Therefore:
Number of even product pairs = Total Number of pairs – Number of odd product pairs
Below is the implementation of above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// function to count odd product pairint count_odd_pair(int n, int a[]){ int odd = 0, even = 0; for (int i = 0; i < n; i++) { // if number is even if (a[i] % 2 == 0) even++; // if number is odd else odd++; } // count of ordered pairs int ans = odd * (odd - 1); return ans;}// function to count even product pairint count_even_pair(int odd_product_pairs, int n){ int total_pairs = (n * (n - 1)); int ans = total_pairs - odd_product_pairs; return ans ;}// Driver codeint main(){ int n = 6; int a[] = { 2, 4, 5, 9, 1, 8 }; int odd_product_pairs = count_odd_pair(n, a); int even_product_pairs = count_even_pair( odd_product_pairs, n); cout << "Even Product Pairs = " << even_product_pairs << endl; cout << "Odd Product Pairs= " << odd_product_pairs << endl; return 0;} |
Java
// Java implementation of the above approach import java.io.*;class GFG { // function to count odd product pair static int count_odd_pair(int n, int a[]) { int odd = 0, even = 0; for (int i = 0; i < n; i++) { // if number is even if (a[i] % 2 == 0) even++; // if number is odd else odd++; } // count of ordered pairs int ans = odd * (odd - 1); return ans; } // function to count even product pair static int count_even_pair(int odd_product_pairs, int n) { int total_pairs = (n * (n - 1)); int ans = total_pairs - odd_product_pairs; return ans;} // Driver code public static void main (String[] args) { int n = 6; int []a = { 2, 4, 5, 9, 1, 8 }; int odd_product_pairs = count_odd_pair(n, a); int even_product_pairs = count_even_pair( odd_product_pairs, n); System.out.println( "Even Product Pairs = "+ even_product_pairs ); System.out.println("Odd Product Pairs= "+ odd_product_pairs ); }}//This Code is Contributed by ajit |
Python3
# Python3 implementation of # above approach# function to count odd product pairdef count_odd_pair(n, a): odd = 0 even = 0 for i in range(0,n): # if number is even if a[i] % 2==0: even=even+1 # if number is odd else: odd=odd+1 # count of ordered pairs ans = odd * (odd - 1) return ans# function to count even product pairdef count_even_pair(odd_product_pairs, n): total_pairs = (n * (n - 1)) ans = total_pairs - odd_product_pairs return ans#Driver codeif __name__=='__main__': n = 6 a = [2, 4, 5, 9, 1 ,8] odd_product_pairs = count_odd_pair(n, a) even_product_pairs = (count_even_pair (odd_product_pairs, n)) print("Even Product Pairs = " ,even_product_pairs) print("Odd Product Pairs= " ,odd_product_pairs)# This code is contributed by # Shashank_Sharma |
C#
// C# implementation of the above approachusing System;public class GFG{ // function to count odd product pair static int count_odd_pair(int n, int []a) { int odd = 0, even = 0; for (int i = 0; i < n; i++) { // if number is even if (a[i] % 2 == 0) even++; // if number is odd else odd++; } // count of ordered pairs int ans = odd * (odd - 1); return ans; } // function to count even product pair static int count_even_pair(int odd_product_pairs, int n) { int total_pairs = (n * (n - 1)); int ans = total_pairs - odd_product_pairs; return ans;} // Driver code static public void Main (){ int n = 6; int []a = { 2, 4, 5, 9, 1, 8 }; int odd_product_pairs = count_odd_pair(n, a); int even_product_pairs = count_even_pair( odd_product_pairs, n); Console.WriteLine( "Even Product Pairs = "+ even_product_pairs ); Console.WriteLine("Odd Product Pairs= "+ odd_product_pairs ); }} |
PHP
<?php// function to count odd product pairfunction count_odd_pair($n, $a){ $odd = 0 ; $even = 0 ; for ($i = 0; $i < $n; $i++) { // if number is even if ($a[$i] % 2 == 0) $even++; // if number is odd else $odd++; } // count of ordered pairs $ans = $odd * ($odd - 1); return $ans;}// function to count even product pairfunction count_even_pair($odd_product_pairs, $n){ $total_pairs = ($n * ($n - 1)); $ans = $total_pairs - $odd_product_pairs; return $ans ;}// Driver code$n = 6;$a = array( 2, 4, 5, 9, 1, 8 );$odd_product_pairs = count_odd_pair($n, $a);$even_product_pairs = count_even_pair($odd_product_pairs, $n);echo "Even Product Pairs = ", $even_product_pairs, "\n";echo "Odd Product Pairs = ", $odd_product_pairs, "\n";// This code is contributed// by ANKITRAI1?> |
Javascript
<script>// JavaScript implementation of the above approach // function to count odd product pair function count_odd_pair(n, a) { let odd = 0, even = 0; for (let i = 0; i < n; i++) { // if number is even if (a[i] % 2 == 0) even++; // if number is odd else odd++; } // count of ordered pairs let ans = odd * (odd - 1); return ans; } // function to count even product pair function count_even_pair(odd_product_pairs, n) { let total_pairs = (n * (n - 1)); let ans = total_pairs - odd_product_pairs; return ans ; } // Driver code let n = 6; let a = [ 2, 4, 5, 9, 1, 8 ]; let odd_product_pairs = count_odd_pair(n, a); let even_product_pairs = count_even_pair( odd_product_pairs, n); document.write("Even Product Pairs = " + even_product_pairs + "<br>"); document.write("Odd Product Pairs= " + odd_product_pairs + "<br>"); // This code is contributed by Surbhi Tyagi.</script> |
Output
Even Product Pairs = 24 Odd Product Pairs= 6
Complexity Analysis:
- Time Complexity: O(n), where n represents the size of the given array.
- Auxiliary Complexity :O(1), no extra space is required, so it is a 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!
