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 sumsstatic 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 functionpublic 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 sumsstatic 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
