Given an array arr[] of N integers, the task is to find a pair with even parity and maximum sum.
Examples:
Input: arr[] = {18, 15, 8, 9, 14}
Output: 18 15
Explanation:
Binary Representation of elements –
18 => 10010, Parity = 2
15 => 1111, Parity = 4
8 => 1000, Parity = 1
9 => 1001, Parity = 2
14 => 1110, Parity = 3
Here, parity for elements 18, 15 and 9 are even
Hence, pair with maximum sum will be 18 and 15Input: arr[] = {5, 3, 4, 2, 9}
Output: 9 5
Explanation:
The array contains three even parity values 5, 3 and 9.
Hence, pair with maximum sum will be 9 and 5.
Approach: The key observation in the problem is if we choose two maximum numbers with even parity, then it will be the desired answer.
Traverse the array and check if the current element is having even parity. Then, update the two maximum numbers with even parity.
if (findParity(arr[i]) % 2 == 0) if (arr[i] >= firstMaximum) secondMaximum = firstMaximum firstMaximum = arr[i] elif (arr[i] >= secondMaximum) secondMaximum = arr[i]
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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
Time Complexity: O(n*log10 n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!