Dada una array de n números positivos, la tarea es contar el número de pares ordenados con sumas pares e impares.
Ejemplos:
Entrada: arr[] = {1, 2, 4}
Salida: pares de sumas pares = 2, pares de sumas impares = 4
Los pares ordenados son (1, 2), (1, 4), (2, 1), (4 , 1), (2, 4), (4, 2)
Pares con suma Par: (2, 4), (4, 2)
Pares con suma Impar: (1, 2), (1, 4), (2 , 1), (4, 1)
Entrada: arr[] = {2, 4, 5, 9, 1, 8}
Salida: pares de sumas pares = 12, pares de sumas impares = 18
Planteamiento:
La suma de dos números es impar si un número es impar y otro es par. Así que ahora tenemos que contar los números pares e impares. Como en el orden par (a, b) y (b, a) ambos tratados como pares diferentes, por lo tanto
Número de pares de sumas impares = (recuento de números pares) * (recuento de números impares) * 2
Esto se debe a que todos los números pares pueden emparejarse con todos los números impares y todos los números impares pueden emparejarse con todos los números pares. Así se multiplica 2 en la respuesta.
Y el número de pares de sumas pares será una inversión del número de pares de sumas impares. Por lo tanto:
Número de pares de sumas pares = Número total de pares – Número de pares de sumas impares
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// function to count odd sum pair
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 * even * 2;
return ans;
}
// function to count even sum pair
int count_even_pair(int odd_sum_pairs, int n)
{
int total_pairs = (n * (n - 1));
int ans = total_pairs - odd_sum_pairs;
return ans;
}
// Driver code
int main()
{
int n = 6;
int a[] = { 2, 4, 5, 9, 1, 8 };
int odd_sum_pairs = count_odd_pair(n, a);
int even_sum_pairs = count_even_pair(
odd_sum_pairs, n);
cout << "Even Sum Pairs = "
<< even_sum_pairs
<< endl;
cout << "Odd Sum Pairs= "
<< odd_sum_pairs
<< endl;
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// function to count odd sum 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 * even * 2;
return ans;
}
// function to count even sum pair
static int count_even_pair(int odd_sum_pairs, int n)
{
int total_pairs = (n * (n - 1));
int ans = total_pairs - odd_sum_pairs;
return ans;
}
// Driver code
public static void main(String []args)
{
int n = 6;
int []a = { 2, 4, 5, 9, 1, 8 };
int odd_sum_pairs = count_odd_pair(n, a);
int even_sum_pairs = count_even_pair( odd_sum_pairs, n);
System.out.println("Even Sum Pairs = " + even_sum_pairs);
System.out.println("Odd Sum Pairs= " + odd_sum_pairs);
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the above approach
# function to count odd sum pair
def 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 * even * 2
return ans
# function to count even sum pair
def count_even_pair( odd_sum_pairs, n):
total_pairs = ( n * ( n - 1))
ans = total_pairs - odd_sum_pairs
return ans
# Driver code
n = 6
a = [2, 4, 5, 9, 1, 8]
odd_sum_pairs = count_odd_pair( n, a)
even_sum_pairs = count_even_pair( odd_sum_pairs, n)
print("Even Sum Pairs =", even_sum_pairs)
print("Odd Sum Pairs=", odd_sum_pairs)
# This code is contributed by ihritik
C#
// C# implementation of the above approach
using System;
class GFG
{
// function to count odd sum 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 * even * 2;
return ans;
}
// function to count even sum pair
static int count_even_pair(int odd_sum_pairs, int n)
{
int total_pairs = (n * (n - 1));
int ans = total_pairs - odd_sum_pairs;
return ans;
}
// Driver code
public static void Main()
{
int n = 6;
int []a = { 2, 4, 5, 9, 1, 8 };
int odd_sum_pairs = count_odd_pair(n, a);
int even_sum_pairs = count_even_pair( odd_sum_pairs, n);
Console.WriteLine("Even Sum Pairs = " + even_sum_pairs);
Console.WriteLine("Odd Sum Pairs= " + odd_sum_pairs);
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// function to count odd sum pair
function 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 * $even * 2;
return $ans;
}
// function to count even sum pair
function count_even_pair($odd_sum_pairs, $n)
{
$total_pairs = ($n * ($n - 1));
$ans = $total_pairs - $odd_sum_pairs;
return $ans;
}
// Driver code
$n = 6;
$a = array( 2, 4, 5, 9, 1, 8 );
$odd_sum_pairs = count_odd_pair($n, $a);
$even_sum_pairs = count_even_pair($odd_sum_pairs, $n);
echo "Even Sum Pairs = $even_sum_pairs \n";
echo "Odd Sum Pairs= $odd_sum_pairs \n";
// This code is contributed by ihritik
?>
Javascript
<script>
// JavaScript implementation of the above approach
// function to count odd sum pair
function count_odd_pair(n, a)
{
var odd = 0, even = 0;
for (var 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
var ans = odd * even * 2;
return ans;
}
// function to count even sum pair
function count_even_pair(odd_sum_pairs, n)
{
var total_pairs = (n * (n - 1));
var ans = total_pairs - odd_sum_pairs;
return ans;
}
// Driver code
var n = 6;
var a = [2, 4, 5, 9, 1, 8];
var odd_sum_pairs = count_odd_pair(n, a);
var even_sum_pairs = count_even_pair(
odd_sum_pairs, n);
document.write( "Even Sum Pairs = "
+ even_sum_pairs + "<br>");
document.write( "Odd Sum Pairs = "
+ odd_sum_pairs + "<br>");
</script>
Even Sum Pairs = 12 Odd Sum Pairs= 18
Complejidad de tiempo: O(n), para encontrar el número de números pares e impares en la array dada
Espacio auxiliar: O(1), ya que no se usa espacio adicional