Given two arrays of N and M integers. The task is to find the number of unordered pairs formed of elements from both arrays in such a way that their sum is an odd number.
Note: An element can only be one pair.
Examples:
Input: a[] = {9, 14, 6, 2, 11}, b[] = {8, 4, 7, 20}
Output: 3
{9, 20}, {14, 7} and {11, 8}
Input: a[] = {2, 4, 6}, b[] = {8, 10, 12}
Output: 0
Approach: Count the number of odd and even numbers in both the arrays and the answer to the number of pairs will be min(odd1, even2) + min(odd2, even1), because odd + even is only odd.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function that returns the number of pairsint count_pairs(int a[], int b[], int n, int m){ // Count of odd and even numbers int odd1 = 0, even1 = 0; int odd2 = 0, even2 = 0; // Traverse in the first array // and count the number of odd // and even numbers in them for (int i = 0; i < n; i++) { if (a[i] % 2) odd1++; else even1++; } // Traverse in the second array // and count the number of odd // and even numbers in them for (int i = 0; i < m; i++) { if (b[i] % 2) odd2++; else even2++; } // Count the number of pairs int pairs = min(odd1, even2) + min(odd2, even1); // Return the number of pairs return pairs;}// Driver codeint main(){ int a[] = { 9, 14, 6, 2, 11 }; int b[] = { 8, 4, 7, 20 }; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); cout << count_pairs(a, b, n, m); return 0;} |
Java
// Java program to implement// the above approachclass GFG { // Function that returns the number of pairs static int count_pairs(int a[], int b[], int n, int m) { // Count of odd and even numbers int odd1 = 0, even1 = 0; int odd2 = 0, even2 = 0; // Traverse in the first array // and count the number of odd // and even numbers in them for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) { odd1++; } else { even1++; } } // Traverse in the second array // and count the number of odd // and even numbers in them for (int i = 0; i < m; i++) { if (b[i] % 2 == 1) { odd2++; } else { even2++; } } // Count the number of pairs int pairs = Math.min(odd1, even2) + Math.min(odd2, even1); // Return the number of pairs return pairs; } // Driver code public static void main(String[] args) { int a[] = { 9, 14, 6, 2, 11 }; int b[] = { 8, 4, 7, 20 }; int n = a.length; int m = b.length; System.out.println(count_pairs(a, b, n, m)); }}// This code contributed by Rajput-Ji |
Python3
# Python 3 program to implement# the above approach# Function that returns # the number of pairsdef count_pairs(a, b, n, m): # Count of odd and even numbers odd1 = 0 even1 = 0 odd2 = 0 even2 = 0 # Traverse in the first array # and count the number of odd # and even numbers in them for i in range(n): if (a[i] % 2): odd1 += 1 else: even1 += 1 # Traverse in the second array # and count the number of odd # and even numbers in them for i in range(m): if (b[i] % 2): odd2 += 1 else: even2 += 1 # Count the number of pairs pairs = (min(odd1, even2) + min(odd2, even1)) # Return the number of pairs return pairs# Driver codeif __name__ == '__main__': a = [9, 14, 6, 2, 11] b = [8, 4, 7, 20] n = len(a) m = len(b) print(count_pairs(a, b, n, m))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to implement// the above approachusing System;class GFG { // Function that returns the number of pairs static int count_pairs(int[] a, int[] b, int n, int m) { // Count of odd and even numbers int odd1 = 0, even1 = 0; int odd2 = 0, even2 = 0; // Traverse in the first array // and count the number of odd // and even numbers in them for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) { odd1++; } else { even1++; } } // Traverse in the second array // and count the number of odd // and even numbers in them for (int i = 0; i < m; i++) { if (b[i] % 2 == 1) { odd2++; } else { even2++; } } // Count the number of pairs int pairs = Math.Min(odd1, even2) + Math.Min(odd2, even1); // Return the number of pairs return pairs; } // Driver code static public void Main() { int[] a = { 9, 14, 6, 2, 11 }; int[] b = { 8, 4, 7, 20 }; int n = a.Length; int m = b.Length; Console.WriteLine(count_pairs(a, b, n, m)); }}// This code contributed by ajit. |
PHP
<?php// PHP program to implement // the above approach // Function that returns the number of pairs function count_pairs($a, $b, $n, $m) { // Count of odd and even numbers $odd1 = 0; $even1 = 0; $odd2 = 0; $even2 = 0; // Traverse in the first array // and count the number of odd // and even numbers in them for ($i = 0; $i < $n; $i++) { if ($a[$i] % 2) $odd1++; else $even1++; } // Traverse in the second array // and count the number of odd // and even numbers in them for ($i = 0; $i < $m; $i++) { if ($b[$i] % 2) $odd2++; else $even2++; } // Count the number of pairs $pairs = min($odd1, $even2) + min($odd2, $even1); // Return the number of pairs return $pairs; } // Driver code $a = array( 9, 14, 6, 2, 11 ); $b = array( 8, 4, 7, 20 ); $n = count($a) ; $m = count($b) ; echo count_pairs($a, $b, $n, $m); // This code is contributed by Ryuga?> |
Javascript
<script>// JavaScript program to implement // the above approach // Function that returns the number of pairs function count_pairs(a, b, n, m) { // Count of odd and even numbers let odd1 = 0, even1 = 0; let odd2 = 0, even2 = 0; // Traverse in the first array // and count the number of odd // and even numbers in them for (let i = 0; i < n; i++) { if (a[i] % 2) odd1++; else even1++; } // Traverse in the second array // and count the number of odd // and even numbers in them for (let i = 0; i < m; i++) { if (b[i] % 2) odd2++; else even2++; } // Count the number of pairs let pairs = Math.min(odd1, even2) + Math.min(odd2, even1); // Return the number of pairs return pairs; } // Driver code let a = [ 9, 14, 6, 2, 11 ]; let b = [ 8, 4, 7, 20 ]; let n = a.length; let m = b.length; document.write(count_pairs(a, b, n, m)); // This code is contributed by Surbhi Tyagi.</script> |
Output:
3
Time Complexity: O(n + m)
Auxiliary Space: 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!
