Given an 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
Method 1 (Naive)
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
C++
// CPP program to count pairs with maximum sum.
#include <bits/stdc++.h>
using namespace std;
// function to find the number of maximum pair sums
int sum(int a[], int n)
{
// traverse through all the pairs
int maxSum = INT_MIN;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
maxSum = 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
int main()
{
int array[] = { 1, 1, 1, 2, 2, 2 };
int n = sizeof(array) / sizeof(array[0]);
cout << sum(array, n);
return 0;
}
Output :
3
Time complexity:O(n^2)
Method 2 (Efficient)
If we take a closer look, we can notice following facts.
- 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
C++
// CPP program to count pairs with maximum sum. #include <bits/stdc++.h> using namespace std; // function to find the number of maximum pair sums int sum(int a[], int n) { // Find maximum and second maximum elements. // Also find their counts. int maxVal = a[0], maxCount = 1; int secondMax = INT_MIN, secondMaxCount; 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 to test the above function int main() { int array[] = { 1, 1, 1, 2, 2, 2, 3 }; int n = sizeof(array) / sizeof(array[0]); cout << sum(array, n); return 0; } |
Output :
3
Time complexity:O(n)
Please refer complete article on Number of pairs with maximum sum for more details!
Share your thoughts in the comments
