Number of pairs with maximum sum
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<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
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<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
Implementation:
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; } |
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 |
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" |
C#
// C# program to count pairs // with maximum sum. using System; 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 = int .MinValue; 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() { int []array = { 1, 1, 1, 2, 2, 2 }; int n = array.Length; Console.WriteLine(sum(array, n)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to count pairs // with maximum sum. // function to find the number // of maximum pair sum function sum( $a , $n ) { // traverse through all // the pairs $maxSum = PHP_INT_MIN; for ( $i = 0; $i < $n ; $i ++) for ( $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 $c = 0; for ( $i = 0; $i < $n ; $i ++) for ( $j = $i + 1; $j < $n ; $j ++) if ( $a [ $i ] + $a [ $j ] == $maxSum ) $c ++; return $c ; } // Driver Code $array = array (1, 1, 1, 2, 2, 2); $n = count ( $array ); echo sum( $array , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to count pairs // with maximum sum. // Function to find the number of // maximum pair sums function sum(a, n) { // traverse through all the pairs let maxSum = Number.MIN_VALUE; for (let i = 0; i < n; i++) for (let 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 let c = 0; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (a[i] + a[j] == maxSum) c++; return c; } // Driver Code let array = [ 1, 1, 1, 2, 2, 2 ]; let n = array.length; document.write(sum(array, n)); // This code is contributed by code_hunt </script> |
Output :
3
Time complexity: O(n2)
Auxiliary Space: O(1)
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
Implementation:
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; } |
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 |
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 |
C#
// C# program to count pairs with maximum // sum. using System; 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 = int .MinValue; int 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() { int []array = { 1, 1, 1, 2, 2, 2, 3 }; int n = array.Length; Console.WriteLine(sum(array, n)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to count // pairs with maximum sum. // function to find the number // of maximum pair sums function sum( $a , $n ) { // Find maximum and second // maximum elements. Also // find their counts. $maxVal = $a [0]; $maxCount = 1; $secondMax = PHP_INT_MIN; $secondMaxCount ; for ( $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 Code $array = array (1, 1, 1, 2, 2, 2, 3 ); $n = count ( $array ); echo sum( $array , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to count pairs with maximum sum. // function to find the number // of maximum pair sums function sum(a, n) { // Find maximum and second maximum // elements. Also find their counts. let maxVal = a[0], maxCount = 1; let secondMax = Number.MIN_VALUE; let secondMaxCount = 0; for (let 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 * parseInt((maxCount - 1) / 2, 10); // If maximum element appears // only once. return secondMaxCount; } let array = [ 1, 1, 1, 2, 2, 2, 3 ]; let n = array.length; document.write(sum(array, n)); // This code is contributed by divyesh072019. </script> |
Output :
3
Time complexity: O(n)
Auxiliary Space: O(1)
Contact Us