Dada una array arr[] y un entero impar N , la tarea es verificar si se pueden seleccionar N números de la array que tiene una suma par . Escriba Sí si es posible. De lo contrario , imprima No.
Ejemplos:
Entrada: arr[] = {9, 2, 3, 4, 1, 8, 7, 7, 6}, N = 5
Salida: Sí
Explicación: {9, 3, 1, 7, 6} son los N elementos que tienen incluso sumaEntrada: arr[] = {1, 3, 7, 9, 3}, N = 3
Salida: No
Enfoque: siga los pasos a continuación para resolver el problema:
- Cuente enteros pares e impares y almacénelos en even_freq y odd_freq respectivamente.
- Si even_freq excede N , entonces tome todos los números pares y su suma será par. Por lo tanto, imprima «Sí».
- De lo contrario, verifique odd_freq .
- Si odd_freq es impar , compruebe si (odd_freq + even_freq – 1) es ≥ N o no. Si es cierto, escriba “ Sí ”.
- Si odd_freq es par , compruebe si (odd_freq + even_freq) es ≥ N o no. Si es cierto, escriba “ Sí ”.
- Si ninguna de las condiciones anteriores cumple, escriba “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ efficient program to check
// if N numbers with Odd sum can be
// selected from the given array
#include <bits/stdc++.h>
using namespace std;
// Function to check if an odd sum can be
// made using N integers from the array
bool checkEvenSum(int arr[], int N, int size)
{
// Initialize odd and even counts
int even_freq = 0, odd_freq = 0;
// Iterate over the array to count
// the no. of even and odd integers
for (int i = 0; i < size; i++) {
// If element is odd
if (arr[i] & 1)
odd_freq++;
// If element is even
else
even_freq++;
}
// Check if even_freq is more than N
if (even_freq >= N)
return true;
else {
// If odd_freq is odd
if (odd_freq & 1) {
// Consider even count of odd
int taken = odd_freq - 1;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req) {
return false;
}
else
return true;
}
else {
int taken = odd_freq;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req) {
return false;
}
else
return true;
}
}
return false;
}
// Driver Code
int main()
{
int arr[] = { 9, 2, 3, 4, 18, 7, 7, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
int N = 5;
if (checkEvenSum(arr, N, size))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
Java
// Java efficient program to check
// if N numbers with Odd sum can be
// selected from the given array
import java.util.*;
class GFG{
// Function to check if an odd sum can be
// made using N integers from the array
static boolean checkEvenSum(int arr[],
int N, int size)
{
// Initialize odd and even counts
int even_freq = 0, odd_freq = 0;
// Iterate over the array to count
// the no. of even and odd integers
for(int i = 0; i < size; i++)
{
// If element is odd
if (arr[i] % 2 == 1)
odd_freq++;
// If element is even
else
even_freq++;
}
// Check if even_freq is more than N
if (even_freq >= N)
return true;
else
{
// If odd_freq is odd
if (odd_freq % 2 == 1)
{
// Consider even count of odd
int taken = odd_freq - 1;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
else
{
int taken = odd_freq;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 9, 2, 3, 4, 18, 7, 7, 6 };
int size = arr.length;
int N = 5;
if (checkEvenSum(arr, N, size))
System.out.print("Yes" + "\n");
else
System.out.print("No" + "\n");
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 efficient program to check
# if N numbers with Odd sum can be
# selected from the given array
# Function to check if an odd sum can be
# made using N integers from the array
def checkEvenSum(arr, N, size):
# Initialize odd and even counts
even_freq , odd_freq = 0 , 0
# Iterate over the array to count
# the no. of even and odd integers
for i in range(size):
# If element is odd
if (arr[i] & 1):
odd_freq += 1
# If element is even
else:
even_freq += 1
# Check if even_freq is more than N
if (even_freq >= N):
return True
else:
# If odd_freq is odd
if (odd_freq & 1):
# Consider even count of odd
taken = odd_freq - 1
# Calculate even required
req = N - taken
# If even count is less
# than required count
if (even_freq < req):
return False
else:
return True
else:
taken = odd_freq
# Calculate even required
req = N - taken
# If even count is less
# than required count
if (even_freq < req):
return False
else:
return True
return False
# Driver Code
if __name__ == "__main__":
arr = [ 9, 2, 3, 4, 18, 7, 7, 6 ]
size = len(arr)
N = 5
if (checkEvenSum(arr, N, size)):
print("Yes")
else:
print("No")
# This code is contributed by chitranayal
C#
// C# efficient program to check
// if N numbers with Odd sum can be
// selected from the given array
using System;
class GFG{
// Function to check if an odd sum can be
// made using N integers from the array
static bool checkEvenSum(int []arr,
int N, int size)
{
// Initialize odd and even counts
int even_freq = 0, odd_freq = 0;
// Iterate over the array to count
// the no. of even and odd integers
for(int i = 0; i < size; i++)
{
// If element is odd
if (arr[i] % 2 == 1)
odd_freq++;
// If element is even
else
even_freq++;
}
// Check if even_freq is more than N
if (even_freq >= N)
return true;
else
{
// If odd_freq is odd
if (odd_freq % 2 == 1)
{
// Consider even count of odd
int taken = odd_freq - 1;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
else
{
int taken = odd_freq;
// Calculate even required
int req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 9, 2, 3, 4, 18, 7, 7, 6 };
int size = arr.Length;
int N = 5;
if (checkEvenSum(arr, N, size))
Console.Write("Yes" + "\n");
else
Console.Write("No" + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript efficient program to check
// if N numbers with Odd sum can be
// selected from the given array
// Function to check if an odd sum can be
// made using N integers from the array
function checkEvenSum(arr, N, size)
{
// Initialize odd and even counts
var even_freq = 0, odd_freq = 0;
// Iterate over the array to count
// the no. of even and odd integers
for(var i = 0; i < size; i++)
{
// If element is odd
if (arr[i] & 1)
odd_freq++;
// If element is even
else
even_freq++;
}
// Check if even_freq is more than N
if (even_freq >= N)
return true;
else
{
// If odd_freq is odd
if (odd_freq & 1)
{
// Consider even count of odd
var taken = odd_freq - 1;
// Calculate even required
var req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
else
{
var taken = odd_freq;
// Calculate even required
var req = N - taken;
// If even count is less
// than required count
if (even_freq < req)
{
return false;
}
else
return true;
}
}
return false;
}
// Driver Code
var arr = [ 9, 2, 3, 4, 18, 7, 7, 6 ];
var size = arr.length;
var N = 5;
if (checkEvenSum(arr, N, size))
document.write("Yes");
else
document.write("No");
// This code is contributed by rrrtnx
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mishrapriyanshu557 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA