Python Program for Number of pairs with maximum sum
Write a python 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
Python 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:
Python3
# Python program to count pairs with # maximum sum def _sum(a, n): # traverse through all the pairs maxSum = - 9999999 for i in range (n): for j in range (n): maxSum = max (maxSum, a[i] + a[j]) # traverse through all pairs and # keep a count of the number # of maximum pairs c = 0 for i in range (n): for j in range (i + 1 , n): if a[i] + a[j] = = maxSum: c + = 1 return c # driver code array = [ 1 , 1 , 1 , 2 , 2 , 2 ] n = len (array) print (_sum(array, n)) # This code is contributed by "Abhishek Sharma 44" |
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:
Python3
# Python 3 program to count # pairs with maximum sum. import sys # Function to find the number # of maximum pair sums def sum (a, n): # Find maximum and second maximum elements. # Also find their counts. maxVal = a[ 0 ] maxCount = 1 secondMax = sys.maxsize for i in range ( 1 , n): if (a[i] = = maxVal): maxCount + = 1 elif (a[i] > maxVal): secondMax = maxVal secondMaxCount = maxCount maxVal = a[i] maxCount = 1 elif (a[i] = = secondMax): secondMax = a[i] secondMaxCount + = 1 elif (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 Code array = [ 1 , 1 , 1 , 2 , 2 , 2 , 3 ] n = len (array) print ( sum (array, n)) # This code is contributed by Smitha Dinesh Semwal |
3
Time complexity: O(n)
Auxiliary Space: O(1)
Please refer complete article on Number of pairs with maximum sum for more details!