Dadas dos arrays de N y M enteros. La tarea es encontrar el número de pares desordenados formados por elementos de ambos arreglos de tal manera que su suma sea un número impar.
Nota : Un elemento solo puede ser un par.
Ejemplos:
Entrada: a[] = {9, 14, 6, 2, 11}, b[] = {8, 4, 7, 20}
Salida: 3
{9, 20}, {14, 7} y {11, 8 }
Entrada: a[] = {2, 4, 6}, b[] = {8, 10, 12}
Salida: 0
Enfoque : Cuente la cantidad de números pares e impares en ambas arrays y la respuesta a la cantidad de pares será min(impar1, par2) + min(impar2, par1), porque impar + par es solo impar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the number of pairs
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)
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 code
int 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 approach
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
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 pairs def 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 code if __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 approach
using 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>
Producción:
3
Complejidad temporal: O(n + m)
Espacio Auxiliar: O(1)