Java Program for Number of pairs with maximum sum
Write a java program for a given array arr[], count number of pairs arr[i], arr[j] such that arr[i] + arr[j] is maximum and i < j.
Example:
Input : arr[] = {1, 1, 1, 2, 2, 2}
Output: 3
Explanation: The maximum possible pair sum where i<j is 4, which is given by 3 pairs, so the answer is 3 the pairs are (2, 2), (2, 2) and (2, 2)Input: arr[] = {1, 4, 3, 3, 5, 1}
Output: 1
Explanation: The pair 4, 5 yields the maximum sum i.e, 9 which is given by 1 pair only
Java program for Number of pairs with maximum sum using Naive Approach:
Traverse a loop i from 0 to n, i.e length of the array and another loop j from i+1 to n to find all possible pairs with i<j. Find the pair with the maximum possible sum, again traverse for all pairs and keep the count of the number of pairs which gives the pair sum equal to maximum .
Below is the Implementation of the above Approach:
Java
// Java program to count pairs // with maximum sum. class GFG { // function to find the number of // maximum pair sums static int sum( int a[], int n) { // traverse through all the pairs int maxSum = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) for ( int j = i + 1 ; j < n; j++) maxSum = Math.max(maxSum, a[i] + a[j]); // traverse through all pairs and // keep a count of the number of // maximum pairs int c = 0 ; for ( int i = 0 ; i < n; i++) for ( int j = i + 1 ; j < n; j++) if (a[i] + a[j] == maxSum) c++; return c; } // driver program to test the above function public static void main(String[] args) { int array[] = { 1 , 1 , 1 , 2 , 2 , 2 }; int n = array.length; System.out.println(sum(array, n)); } } // This code is contributed by Prerna Saini |
3
Time complexity: O(n2)
Auxiliary Space: O(1)
Efficient Method:
- Maximum element is always part of solution.
- If maximum element appears more than once, then result is maxCount * (maxCount – 1)/2. We basically need to choose 2 elements from maxCount (maxCountC2).
- If maximum element appears once, then result is equal to count of second maximum element. We can form a pair with every second max and max.
Below is the Implementation of the above Approach:
Java
// Java program to count pairs // with maximum sum. import java.io.*; class GFG { // function to find the number // of maximum pair sums static int sum( int a[], int n) { // Find maximum and second maximum // elements. Also find their counts. int maxVal = a[ 0 ], maxCount = 1 ; int secondMax = Integer.MIN_VALUE, secondMaxCount = 0 ; for ( int i = 1 ; i < n; i++) { if (a[i] == maxVal) maxCount++; else if (a[i] > maxVal) { secondMax = maxVal; secondMaxCount = maxCount; maxVal = a[i]; maxCount = 1 ; } else if (a[i] == secondMax) { secondMax = a[i]; secondMaxCount++; } else if (a[i] > secondMax) { secondMax = a[i]; secondMaxCount = 1 ; } } // If maximum element appears // more than once. if (maxCount > 1 ) return maxCount * (maxCount - 1 ) / 2 ; // If maximum element appears // only once. return secondMaxCount; } // driver program public static void main(String[] args) { int array[] = { 1 , 1 , 1 , 2 , 2 , 2 , 3 }; int n = array.length; System.out.println(sum(array, n)); } } // This code is contributed by Prerna Saini |
3
Time complexity: O(n)
Auxiliary Space: O(1)
Please refer complete article on Number of pairs with maximum sum for more details!