Encuentre el par de suma máxima en una array con paridad par

Dada una array arr[] de N enteros, la tarea es encontrar un par con paridad par y suma máxima.

Ejemplos:

Entrada: arr[] = {18, 15, 8, 9, 14} 
Salida: 18 15 
Explicación: 
Representación binaria de elementos – 
18 => 10010, Paridad = 2 
15 => 1111, Paridad = 4 
8 => 1000, Paridad = 1 
9 => 1001, Paridad = 2 
14 => 1110, Paridad = 3 
Aquí, la paridad para los elementos 18, 15 y 9 son pares 
Por lo tanto, el par con suma máxima será 18 y 15

Entrada: arr[] = {5, 3, 4, 2, 9} 
Salida: 9 5 
Explicación: 
La array contiene tres valores de paridad par 5, 3 y 9. 
Por lo tanto, el par con suma máxima será 9 y 5.  

Planteamiento: La observación clave en el problema es que si elegimos dos números máximos con paridad par, entonces será la respuesta deseada.
Recorra la array y verifique si el elemento actual tiene paridad par . Luego, actualice los dos números máximos con paridad par. 

if (findParity(arr[i]) % 2 == 0)
    if (arr[i] >= firstMaximum)
         secondMaximum = firstMaximum
         firstMaximum  = arr[i]
    elif (arr[i] >= secondMaximum)
         secondMaximum = arr[i]

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find
// a pair with even parity and
// maximum sum
 
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e3;
 
// Function that returns true
// if count of set bits
// in given number is even
bool isEvenParity(int x)
{
    // Parity will store the
    // count of set bits
    int parity = 0;
    while (x != 0) {
        if (x & 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
 
// Function to print the
// elements of the array
void printArray(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        cout << arr[i] << ' ';
    }
}
 
// Function to remove all the
// even parity elements from
// the given array
void findPairEvenParity(
            int arr[], int len)
{
    int firstMaximum = INT_MIN;
    int secondMaximum = INT_MIN;
     
    // Traverse the array
    for (int i = 0; i < len; i++) {
 
        // If the current element
        // has even parity
        if (isEvenParity(arr[i])) {
 
            if (arr[i] >= firstMaximum){
                secondMaximum = firstMaximum;
                firstMaximum = arr[i];
            }
            else if (arr[i] >= secondMaximum){
                secondMaximum = arr[i];
            }
        }
    }
     
    cout << firstMaximum
         << " " << secondMaximum;
}
 
// Driver Code
int main()
{
    int arr[] = { 18, 15, 8, 9, 14 };
    int len = sizeof(arr) / sizeof(int);
     
    // Function Call
    findPairEvenParity(arr, len);
 
    return 0;
}

// Java implementation to find
// a pair with even parity and
// maximum sum
import java.util.*;
 
class GFG{
 
static int sz = (int) 1e3;
 
// Function that returns true
// if count of set bits
// in given number is even
static boolean isEvenParity(int x)
{
     
    // Parity will store the
    // count of set bits
    int parity = 0;
     
    while (x != 0)
    {
        if (x % 2 == 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
 
// Function to print the
// elements of the array
static void printArray(int arr[],
                       int len)
{
    for(int i = 0; i < len; i++)
    {
       System.out.print(arr[i] + " ");
    }
}
 
// Function to remove all the
// even parity elements from
// the given array
static void findPairEvenParity(int arr[],
                               int len)
{
    int firstMaximum = Integer.MIN_VALUE;
    int secondMaximum = Integer.MIN_VALUE;
     
    // Traverse the array
    for(int i = 0; i < len; i++)
    {
        
       // If the current element
       // has even parity
       if (isEvenParity(arr[i]))
       {
           if (arr[i] >= firstMaximum)
           {
               secondMaximum = firstMaximum;
               firstMaximum = arr[i];
           }
           else if (arr[i] >= secondMaximum)
           {
               secondMaximum = arr[i];
           }
       }
    }
    System.out.print(firstMaximum + " " +
                     secondMaximum);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 18, 15, 8, 9, 14 };
    int len = arr.length;
     
    // Function Call
    findPairEvenParity(arr, len);
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to find
# a pair with even parity and
# maximum sum
import sys
 
sz = 1e3
 
# Function that returns true
# if count of set bits
# in given number is even
def isEvenParity(x):
     
    # Parity will store the
    # count of set bits
    parity = 0
     
    while x != 0:
        if (x & 1):
            parity = parity + 1;
         
        x = x >> 1
     
    if (parity % 2 == 0):
        return True
    else:
        return False
 
# Function to print the
# elements of the array
def printArray(arr, n):
     
    for i in range(0, n):
        print(arr[i], end = ' ')
     
# Function to remove all the
# even parity elements from
# the given array
def findPairEvenParity(arr, n):
     
    firstMaximum = -1
    secondMaximum = -1
     
    # Traverse the array
    for i in range(0, n):
         
        # If the current element
        # has even parity
        if isEvenParity(arr[i]) == True:
            if (arr[i] >= firstMaximum):
                secondMaximum = firstMaximum
                firstMaximum = arr[i]
             
            elif (arr[i] >= secondMaximum):
                secondMaximum = arr[i]
     
    print(firstMaximum, secondMaximum)
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 18, 15, 8, 9, 14 ]
    n = len(arr)
     
    # Function call
    findPairEvenParity(arr, n)
 
# This code is contributed by akhilsaini

// C# implementation to find
// a pair with even parity and
// maximum sum
using System;
class GFG{
 
static int sz = (int) 1e3;
 
// Function that returns true
// if count of set bits
// in given number is even
static bool isEvenParity(int x)
{
     
    // Parity will store the
    // count of set bits
    int parity = 0;
     
    while (x != 0)
    {
        if (x % 2 == 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
 
// Function to print the
// elements of the array
static void printArray(int []arr,
                       int len)
{
    for(int i = 0; i < len; i++)
    {
        Console.Write(arr[i] + " ");
    }
}
 
// Function to remove all the
// even parity elements from
// the given array
static void findPairEvenParity(int []arr,
                               int len)
{
    int firstMaximum = Int32.MinValue;
    int secondMaximum = Int32.MinValue;
     
    // Traverse the array
    for(int i = 0; i < len; i++)
    {
         
        // If the current element
        // has even parity
        if (isEvenParity(arr[i]))
        {
            if (arr[i] >= firstMaximum)
            {
                secondMaximum = firstMaximum;
                firstMaximum = arr[i];
            }
            else if (arr[i] >= secondMaximum)
            {
                secondMaximum = arr[i];
            }
        }
    }
    Console.Write(firstMaximum + " " +
                  secondMaximum);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 18, 15, 8, 9, 14 };
    int len = arr.Length;
     
    // Function Call
    findPairEvenParity(arr, len);
}
}
 
// This code is contributed by Code_Mech

<script>
// Javascript implementation to find
// a pair with even parity and
// maximum sum
 
let sz = 1e3;
  
// Function that returns true
// if count of set bits
// in given number is even
function isEvenParity(x)
{
      
    // Parity will store the
    // count of set bits
    let parity = 0;
      
    while (x != 0)
    {
        if (x % 2 == 1)
            parity++;
        x = x >> 1;
    }
  
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
  
// Function to print the
// elements of the array
function printArray(arr, len)
{
    for(let i = 0; i < len; i++)
    {
       document.write(arr[i] + " ");
    }
}
  
// Function to remove all the
// even parity elements from
// the given array
function findPairEvenParity(arr, len)
{
    let firstMaximum = Number.MIN_VALUE;
    let secondMaximum = Number.MIN_VALUE;
      
    // Traverse the array
    for(let i = 0; i < len; i++)
    {
         
       // If the current element
       // has even parity
       if (isEvenParity(arr[i]))
       {
           if (arr[i] >= firstMaximum)
           {
               secondMaximum = firstMaximum;
               firstMaximum = arr[i];
           }
           else if (arr[i] >= secondMaximum)
           {
               secondMaximum = arr[i];
           }
       }
    }
    document.write(firstMaximum + " " +
                     secondMaximum);
}
 
// Driver Code
     
      let arr = [ 18, 15, 8, 9, 14 ];
    let len = arr.length;
      
    // Function Call
    findPairEvenParity(arr, len);;
            
</script>

18 15

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)