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> |
3
Time Complexity: O(n + m)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
