Dada una array arr[] , la tarea es verificar si es posible hacer que la suma de la array sea impar de modo que se puedan elegir dos índices i y j y arr[i] se pueda establecer igual a arr[j] dado que yo != j .
Ejemplos:
Entrada: arr[] = { 5, 4, 4, 5, 1, 3 }
Salida: Sí
Explicación:
La suma de la array es 22. Ponga arr[0] = arr[1] donde i=0 y j=1 . La suma de esta nueva array es 21, que es impar.
Entrada: arr[] = { 2, 2, 8, 8 }
Salida: No
Explicación:
La suma de la array es 20.
La suma de la array no puede cambiar a impar ya que todos los elementos son pares. Sumar un número par a un número par siempre da un resultado par.
Enfoque: La idea es encontrar la suma de todos los elementos en la array y verificar simultáneamente la cantidad de números pares e impares presentes en la array. Si la suma es par, entonces uno de los números pares se puede reemplazar con un número impar, lo que hace que la suma de la array sea impar. Si no hay elementos impares en el arreglo, entonces la suma del arreglo no puede hacerse impar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if the array
// with odd sum is possible
#include <bits/stdc++.h>
using namespace std;
// Function to check if the
// sum of the array can be made odd.
bool isOdd(int arr[], int n)
{
int l, r, flag = 0, flag1 = 0, sum = 0;
// Find sum of all elements and increment
// check for odd or even elements in the array
// so that by changing ai=aj,
// the sum of the array can be made odd
for (int i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 2 == 0 && flag == 0) {
flag = 1;
l = arr[i];
}
if (arr[i] % 2 != 0 && flag1 == 0) {
r = arr[i];
flag1 = 1;
}
}
// If the sum is already odd
if (sum % 2 != 0) {
return true;
}
// Else, then both the flags should be checked.
// Here, flag1 and flag represent if there is
// an odd-even pair which can be replaced.
else {
if (flag1 == 1 && flag == 1)
return true;
else
return false;
}
}
// Driver code
int main()
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(ar) / sizeof(ar[0]);
bool res = isOdd(ar, n);
if (res)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program to check if the array
// with odd sum is possible
class GFG {
// Function to check if the
// sum of the array can be made odd.
static boolean isOdd(int []arr, int n)
{
int l, r, flag = 0, flag1 = 0, sum = 0;
// Find sum of all elements and increment
// check for odd or even elements in the array
// so that by changing ai=aj,
// the sum of the array can be made odd
for (int i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 2 == 0 && flag == 0) {
flag = 1;
l = arr[i];
}
if (arr[i] % 2 != 0 && flag1 == 0) {
r = arr[i];
flag1 = 1;
}
}
// If the sum is already odd
if (sum % 2 != 0) {
return true;
}
// Else, then both the flags should be checked.
// Here, flag1 and flag represent if there is
// an odd-even pair which can be replaced.
else {
if (flag1 == 1 && flag == 1)
return true;
else
return false;
}
}
// Driver code
public static void main (String[] args)
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = ar.length;
boolean res = isOdd(ar, n);
if (res == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to check if the array
# with odd sum is possible
# Function to check if the
# sum of the array can be made odd.
def isOdd(arr, n) :
flag = 0; flag1 = 0; sum = 0;
# Find sum of all elements and increment
# check for odd or even elements in the array
# so that by changing ai=aj,
# the sum of the array can be made odd
for i in range(n) :
sum += arr[i];
if (arr[i] % 2 == 0 and flag == 0) :
flag = 1;
l = arr[i];
if (arr[i] % 2 != 0 and flag1 == 0) :
r = arr[i];
flag1 = 1;
# If the sum is already odd
if (sum % 2 != 0) :
return True;
# Else, then both the flags should be checked.
# Here, flag1 and flag represent if there is
# an odd-even pair which can be replaced.
else :
if (flag1 == 1 and flag == 1) :
return True;
else :
return False;
# Driver code
if __name__ == "__main__" :
arr = [ 5, 4, 4, 5, 1, 3 ];
n = len(arr);
res = isOdd(arr, n);
if (res) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# program to check if the array
// with odd sum is possible
using System;
class GFG{
// Function to check if the
// sum of the array can be made odd.
static bool isOdd(int[] arr, int n)
{
int flag = 0, flag1 = 0, sum = 0;
// Find sum of all elements and increment
// check for odd or even elements in the array
// so that by changing ai=aj,
// the sum of the array can be made odd
for (int i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 2 == 0 && flag == 0) {
flag = 1;
}
if (arr[i] % 2 != 0 && flag1 == 0) {
flag1 = 1;
}
}
// If the sum is already odd
if (sum % 2 != 0) {
return true;
}
// Else, then both the flags should be checked.
// Here, flag1 and flag represent if there is
// an odd-even pair which can be replaced.
else {
if (flag1 == 1 && flag == 1)
return true;
else
return false;
}
}
// Driver code
static public void Main ()
{
int[] ar = { 5, 4, 4, 5, 1, 3 };
int n = ar.Length;
bool res = isOdd(ar, n);
if (res)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by shivanisingh
Javascript
<script>
// Javascript program to check if the array
// with odd sum is possible
// Function to check if the
// sum of the array can be made odd.
function isOdd(arr, n)
{
let l, r, flag = 0, flag1 = 0, sum = 0;
// Find sum of all elements and increment
// check for odd or even elements in the array
// so that by changing ai=aj,
// the sum of the array can be made odd
for (let i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 2 == 0 && flag == 0) {
flag = 1;
l = arr[i];
}
if (arr[i] % 2 != 0 && flag1 == 0) {
r = arr[i];
flag1 = 1;
}
}
// If the sum is already odd
if (sum % 2 != 0) {
return true;
}
// Else, then both the flags should be checked.
// Here, flag1 and flag represent if there is
// an odd-even pair which can be replaced.
else {
if (flag1 == 1 && flag == 1)
return true;
else
return false;
}
}
// Driver Code
let ar = [ 5, 4, 4, 5, 1, 3 ];
let n = ar.length;
let res = isOdd(ar, n);
if (res == true)
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(N)