Maximum even sum of a pair of given Array
Given an array arr[] of N distinct non-negative integers, the task is to determine if there is an even number that can be represented as the sum of two different elements of arr. If it exists return the maximum such number otherwise return -1.
Examples:
Input: N = 4, arr[] = {2, 3, 4, 5}
Output: 8
Explanation: The values that can be represented as the sum of two distinct elements of arr are 5, 6, 7, 8 and 9.
We have two even number here, and the maximum is 8.Input: N = 2, arr[] = {0, 3}
Output: -1
Explanation: The value represented as the sum of two distinct elements of arr is 1.
We have no even number here, so -1 should be printed.
Naive Approach: The basic approach is:
Consider each pair sum by nested traversal and consider the maximum of all such pair sums that are even and present in the array.
Follow the steps to solve the problem:
- Initialize the result as 0 at starting.
- Traverse the array using a loop from 0 to N – 2
- For each element consider pairing with every element in the range i + 1 to N – 1 and check if the pair sum is even or odd.
- If the sum is even, update the result with the maximum pair sum at each step.
- For each element consider pairing with every element in the range i + 1 to N – 1 and check if the pair sum is even or odd.
- At last, check if the result is 0 then return -1 otherwise return the result.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum even pair sum int maxEvenSumPair( int arr[], int n) { int result = 0; for ( int i = 0; i < (n - 1); i++) { for ( int j = (i + 1); j < n; j++) { // Calculate the sum for each // pair int curSum = arr[i] + arr[j]; // If sum is even than consider // it for result if (curSum % 2 == 0) // Maintain maximum pair // sum in result result = max(result, curSum); } } // If result is zero that means // no pair with even sum is present if (result == 0) return -1; return result; } // Driver code int main() { int arr[] = { 2, 3, 4, 5 }; int size = sizeof (arr) / sizeof (arr[0]); // Function call cout << maxEvenSumPair(arr, size); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find maximum even pair sum public static int maxEvenSumPair( int arr[], int n) { int result = 0 ; for ( int i = 0 ; i < (n - 1 ); i++) { for ( int j = (i + 1 ); j < n; j++) { // Calculate the sum for each // pair int curSum = arr[i] + arr[j]; // If sum is even than consider // it for result if (curSum % 2 == 0 ) // Maintain maximum pair // sum in result result = max(result, curSum); } } // If result is zero that means // no pair with even sum is present if (result == 0 ) return - 1 ; return result; } public static int max( int a, int b) { if (a > b) return a; return b; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 3 , 4 , 5 }; int size = arr.length; // Function call System.out.println(maxEvenSumPair(arr, size)); } } // This code is contributed by ajaymakvana |
Python3
# Python3 program for the above approach # Function to find maximum even pair sum def maxEvenSumPair(arr, n) : result = 0 ; for i in range (n - 1 ) : for j in range (i + 1 , n) : # Calculate the sum for each # pair curSum = arr[i] + arr[j]; # If sum is even than consider # it for result if (curSum % 2 = = 0 ) : # Maintain maximum pair # sum in result result = max (result, curSum); # If result is zero that means # no pair with even sum is present if (result = = 0 ) : return - 1 ; return result; # Driver code if __name__ = = "__main__" : arr = [ 2 , 3 , 4 , 5 ]; size = len (arr); # Function call print (maxEvenSumPair(arr, size)); # This code is contributed by AnkThon |
C#
using System; class HelloWorld { // Function to find maximum even pair sum static int maxEvenSumPair( int [] arr, int n) { int result = 0; for ( int i = 0; i < (n - 1); i++) { for ( int j = (i + 1); j < n; j++) { // Calculate the sum for each // pair int curSum = arr[i] + arr[j]; // If sum is even than consider // it for result if (curSum % 2 == 0) // Maintain maximum pair // sum in result result = Math.Max(result, curSum); } } // If result is zero that means // no pair with even sum is present if (result == 0) return -1; return result; } static void Main() { int [] arr = { 2, 3, 4, 5 }; int size = 4; // Function call Console.Write(maxEvenSumPair(arr, size)); } } // This code is contributed by garg28harsh. |
Javascript
<script> // JavaScript code for the above approach // Function to find maximum even pair sum function maxEvenSumPair(arr, n) { let result = 0; for (let i = 0; i < (n - 1); i++) { for (let j = (i + 1); j < n; j++) { // Calculate the sum for each // pair let curSum = arr[i] + arr[j]; // If sum is even than consider // it for result if (curSum % 2 == 0) // Maintain maximum pair // sum in result result = Math.max(result, curSum); } } // If result is zero that means // no pair with even sum is present if (result == 0) return -1; return result; } // Driver code let arr = [2, 3, 4, 5]; let size = arr.length; // Function call document.write(maxEvenSumPair(arr, size)); // This code is contributed by Potta Lokesh </script> |
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Find maximum sum Pair by finding maximum even and odd numbers:
To solve the problem efficiently follow the below idea:
The key point/ idea is that sum of any two even numbers or any two odd numbers is always even. Find two greatest even numbers and two greatest odd numbers, the final result will be the maximum sum of the two odd numbers and the sum of the two even numbers.
Follow the steps to solve the problem:
- Initialize first and second maximum odd and even numbers equal to -1.
- Traverse the array to find the first maximum even and first maximum odd number.
- Traverse the array a second time to find the second maximum odd and second maximum even number.
- Calculate the sum of the pair of maximum two odd and the pair of maximum two even numbers and consider the result equal to the maximum among them.
- If the result is zero it means no even sum pair exist so return -1, otherwise return the maximum result.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find maximum even pair sum int maxEvenSumPair( int arr[], int n) { int firstEvenMax = -1, secondEvenMax = -1, firstOddMax = -1, secondOddMax = -1; // First traversal for finding // the maximum even and odd number for ( int i = 0; i < n; i++) { if (arr[i] & 1) firstOddMax = max(firstOddMax, arr[i]); else firstEvenMax = max(firstEvenMax, arr[i]); } // Second traversal for finding // the second maximum even and // odd number for ( int i = 0; i < n; i++) { if (arr[i] & 1) { if (arr[i] != firstOddMax) secondOddMax = max(secondOddMax, arr[i]); } else { if (arr[i] != firstEvenMax) secondEvenMax = max(secondEvenMax, arr[i]); } } int sumOdd = 0, sumEven = 0; // If two even numbers exist in array if (firstEvenMax != -1 and secondEvenMax != -1) sumEven = firstEvenMax + secondEvenMax; // If two odd numbers exist in array if (firstOddMax != -1 and secondOddMax != -1) sumOdd = firstOddMax + secondOddMax; int res = max(sumEven, sumOdd); // No even sum pair found so return -1 if (res == 0) return -1; return res; } // Driver code int main() { int arr[] = { 2, 3, 4, 5 }; int size = sizeof (arr) / sizeof (arr[0]); // Function Call cout << maxEvenSumPair(arr, size); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find maximum even pair sum static int maxEvenSumPair( int arr[], int n) { int firstEvenMax = - 1 , secondEvenMax = - 1 , firstOddMax = - 1 , secondOddMax = - 1 ; // First traversal for finding // the maximum even and odd number for ( int i = 0 ; i < n; i++) { if ((arr[i] & 1 )== 1 ) firstOddMax = Math.max(firstOddMax, arr[i]); else firstEvenMax = Math.max(firstEvenMax, arr[i]); } // Second traversal for finding // the second maximum even and // odd number for ( int i = 0 ; i < n; i++) { if ((arr[i] & 1 )== 1 ) { if (arr[i] != firstOddMax) secondOddMax = Math.max(secondOddMax, arr[i]); } else { if (arr[i] != firstEvenMax) secondEvenMax = Math.max(secondEvenMax, arr[i]); } } int sumOdd = 0 , sumEven = 0 ; // If two even numbers exist in array if (firstEvenMax != - 1 && secondEvenMax != - 1 ) sumEven = firstEvenMax + secondEvenMax; // If two odd numbers exist in array if (firstOddMax != - 1 && secondOddMax != - 1 ) sumOdd = firstOddMax + secondOddMax; int res = Math.max(sumEven, sumOdd); // No even sum pair found so return -1 if (res == 0 ) return - 1 ; return res; } // Driver code public static void main (String[] args) { int arr[] = { 2 , 3 , 4 , 5 }; int size = arr.length; // Function Call System.out.println(maxEvenSumPair(arr, size)); } } // This code is contributed by Pushpesh Raj. |
Python3
# Python3 code to implement the approach # Function to find maximum even pair sum def maxEvenSumPair(arr, n) : firstEvenMax = - 1 ; secondEvenMax = - 1 ; firstOddMax = - 1 ; secondOddMax = - 1 ; # First traversal for finding # the maximum even and odd number for i in range (n) : if (arr[i] & 1 ) : firstOddMax = max (firstOddMax, arr[i]); else : firstEvenMax = max (firstEvenMax, arr[i]); # Second traversal for finding # the second maximum even and # odd number for i in range (n) : if (arr[i] & 1 ) : if (arr[i] ! = firstOddMax) : secondOddMax = max (secondOddMax, arr[i]); else : if (arr[i] ! = firstEvenMax) : secondEvenMax = max (secondEvenMax, arr[i]); sumOdd = 0 ; sumEven = 0 ; # If two even numbers exist in array if (firstEvenMax ! = - 1 and secondEvenMax ! = - 1 ) : sumEven = firstEvenMax + secondEvenMax; # If two odd numbers exist in array if (firstOddMax ! = - 1 and secondOddMax ! = - 1 ) : sumOdd = firstOddMax + secondOddMax; res = max (sumEven, sumOdd); # No even sum pair found so return -1 if (res = = 0 ) : return - 1 ; return res; # Driver code if __name__ = = "__main__" : arr = [ 2 , 3 , 4 , 5 ]; size = len (arr); # Function Call print (maxEvenSumPair(arr, size)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; class GFG { // Function to find maximum even pair sum static int maxEvenSumPair( int [] arr, int n) { int firstEvenMax = -1, secondEvenMax = -1, firstOddMax = -1, secondOddMax = -1; // First traversal for finding // the maximum even and odd number for ( int i = 0; i < n; i++) { if ((arr[i] & 1) != 0) firstOddMax = Math.Max(firstOddMax, arr[i]); else firstEvenMax = Math.Max(firstEvenMax, arr[i]); } // Second traversal for finding // the second maximum even and // odd number for ( int i = 0; i < n; i++) { if ((arr[i] & 1) != 0) { if (arr[i] != firstOddMax) secondOddMax = Math.Max(secondOddMax, arr[i]); } else { if (arr[i] != firstEvenMax) secondEvenMax = Math.Max(secondEvenMax, arr[i]); } } int sumOdd = 0, sumEven = 0; // If two even numbers exist in array if (firstEvenMax != -1 && secondEvenMax != -1) sumEven = firstEvenMax + secondEvenMax; // If two odd numbers exist in array if (firstOddMax != -1 && secondOddMax != -1) sumOdd = firstOddMax + secondOddMax; int res = Math.Max(sumEven, sumOdd); // No even sum pair found so return -1 if (res == 0) return -1; return res; } static void Main() { int [] arr = { 2, 3, 4, 5 }; int size = arr.Length; // Function Call Console.Write(maxEvenSumPair(arr, size)); } } // This code is contributed by garg28harsh. |
Javascript
<script> // Javascript code to implement the approach // Function to find maximum even pair sum function maxEvenSumPair(arr, n) { let firstEvenMax = -1; let secondEvenMax = -1; let firstOddMax = -1; let secondOddMax = -1; // First traversal for finding // the maximum even and odd number for (let i = 0; i < n; i++) { if (arr[i] & 1) firstOddMax = Math.max(firstOddMax, arr[i]); else firstEvenMax = Math.max(firstEvenMax, arr[i]); } // Second traversal for finding // the second maximum even and // odd number for (let i = 0; i < n; i++) { if (arr[i] & 1) { if (arr[i] != firstOddMax) secondOddMax = Math.max(secondOddMax, arr[i]); } else { if (arr[i] != firstEvenMax) secondEvenMax = Math.max(secondEvenMax, arr[i]); } } let sumOdd = 0; let sumEven = 0; // If two even numbers exist in array if (firstEvenMax != -1 && secondEvenMax != -1) sumEven = firstEvenMax + secondEvenMax; // If two odd numbers exist in array if (firstOddMax != -1 && secondOddMax != -1) sumOdd = firstOddMax + secondOddMax; let res = Math.max(sumEven, sumOdd); // No even sum pair found so return -1 if (res == 0) return -1; return res; } // Driver code let arr = [ 2, 3, 4, 5 ]; let size = arr.length; // Function Call console.log(maxEvenSumPair(arr, size)); // This code is contributed by akashish__ </script> |
8
Time Complexity: O(N)
Auxiliary Space: O(1)