Pair with largest sum which is less than K in the array
Given an array arr of size N and an integer K. The task is to find the pair of integers such that their sum is maximum and but less than K
Examples:
Input : arr = {30, 20, 50} , K = 70
Output : 30, 20
30 + 20 = 50, which is the maximum possible sum which is less than K
Input : arr = {5, 20, 110, 100, 10}, K = 85
Output : 20, 10
Approach :
An efficient approach is to sort the given array and find the element which is greater than or equal to K. If found at index p, we have to find pairs only between arr[0, …, p-1]. Run nested loops. One to take care of the first element in the pair and the other to take care of the second element in the pair. Maintain a variable maxsum and two other variables a and b to keep track of the possible solution. Initialize maxsum to 0. Find A[i] + A[j] (assuming i runs in the outer loop and j in the inner loop). If it is greater than maxsum then update maxsum with this sum and change a and b to the i’th and j’th elements of this array.
Below is the implementation of the above approach :
C++
// CPP program to find pair with largest // sum which is less than K in the array #include <bits/stdc++.h> using namespace std; // Function to find pair with largest // sum which is less than K in the array void Max_Sum( int arr[], int n, int k) { // To store the break point int p = n; // Sort the given array sort(arr, arr + n); // Find the break point for ( int i = 0; i < n; i++) { // No need to look beyond i'th index if (arr[i] >= k) { p = i; break ; } } int maxsum = 0, a, b; // Find the required pair for ( int i = 0; i < p; i++) { for ( int j = i + 1; j < p; j++) { if (arr[i] + arr[j] < k and arr[i] + arr[j] > maxsum) { maxsum = arr[i] + arr[j]; a = arr[i]; b = arr[j]; } } } // Print the required answer cout << a << " " << b; } // Driver code int main() { int arr[] = {5, 20, 110, 100, 10}, k = 85; int n = sizeof (arr) / sizeof (arr[0]); // Function call Max_Sum(arr, n, k); return 0; } |
Java
// Java program to find pair with largest // sum which is less than K in the array import java.util.Arrays; class GFG { // Function to find pair with largest // sum which is less than K in the array static void Max_Sum( int arr[], int n, int k) { // To store the break point int p = n; // Sort the given array Arrays.sort(arr); // Find the break point for ( int i = 0 ; i < n; i++) { // No need to look beyond i'th index if (arr[i] >= k) { p = i; break ; } } int maxsum = 0 , a = 0 , b = 0 ; // Find the required pair for ( int i = 0 ; i < p; i++) { for ( int j = i + 1 ; j < p; j++) { if (arr[i] + arr[j] < k && arr[i] + arr[j] > maxsum) { maxsum = arr[i] + arr[j]; a = arr[i]; b = arr[j]; } } } // Print the required answer System.out.print( a + " " + b); } // Driver code public static void main (String[] args) { int []arr = { 5 , 20 , 110 , 100 , 10 }; int k = 85 ; int n = arr.length; // Function call Max_Sum(arr, n, k); } } // This code is contributed by anuj_67.. |
Python3
# Python3 program to find pair with largest # sum which is less than K in the array # Function to find pair with largest # sum which is less than K in the array def Max_Sum(arr, n, k): # To store the break point p = n # Sort the given array arr.sort() # Find the break point for i in range ( 0 , n): # No need to look beyond i'th index if (arr[i] > = k): p = i break maxsum = 0 a = 0 b = 0 # Find the required pair for i in range ( 0 , p): for j in range (i + 1 , p): if (arr[i] + arr[j] < k and arr[i] + arr[j] > maxsum): maxsum = arr[i] + arr[j] a = arr[i] b = arr[j] # Print the required answer print (a, b) # Driver code arr = [ 5 , 20 , 110 , 100 , 10 ] k = 85 n = len (arr) # Function call Max_Sum(arr, n, k) # This code is contributed by Sanjit_Prasad |
C#
// C# program to find pair with largest // sum which is less than K in the array using System; class GFG { // Function to find pair with largest // sum which is less than K in the array static void Max_Sum( int []arr, int n, int k) { // To store the break point int p = n; // Sort the given array Array.Sort(arr); // Find the break point for ( int i = 0; i < n; i++) { // No need to look beyond i'th index if (arr[i] >= k) { p = i; break ; } } int maxsum = 0, a = 0, b = 0; // Find the required pair for ( int i = 0; i < p; i++) { for ( int j = i + 1; j < p; j++) { if (arr[i] + arr[j] < k && arr[i] + arr[j] > maxsum) { maxsum = arr[i] + arr[j]; a = arr[i]; b = arr[j]; } } } // Print the required answer Console.WriteLine( a + " " + b); } // Driver code public static void Main () { int []arr = {5, 20, 110, 100, 10}; int k = 85; int n = arr.Length; // Function call Max_Sum(arr, n, k); } } // This code is contributed by anuj_67.. |
Javascript
<script> // Javascript program to find pair with largest // sum which is less than K in the array // Function to find pair with largest // sum which is less than K in the array function Max_Sum(arr, n, k) { // To store the break point let p = n; // Sort the given array arr.sort( function (a, b){ return a - b}); // Find the break point for (let i = 0; i < n; i++) { // No need to look beyond i'th index if (arr[i] >= k) { p = i; break ; } } let maxsum = 0, a = 0, b = 0; // Find the required pair for (let i = 0; i < p; i++) { for (let j = i + 1; j < p; j++) { if (arr[i] + arr[j] < k && arr[i] + arr[j] > maxsum) { maxsum = arr[i] + arr[j]; a = arr[i]; b = arr[j]; } } } // Print the required answer document.write( a + " " + b + "</br>" ); } let arr = [5, 20, 110, 100, 10]; let k = 85; let n = arr.length; // Function call Max_Sum(arr, n, k); </script> |
10 20
Time complexity: O(N^2)
Auxiliary Space: O(1)
Efficient Approach: Two Pointer Method
After sorting, we can place two pointers at the left and right extremes of the array. The desired pair can be found by the following steps:
- Find the current sum of the values at both the pointers.
- If the sum is lesser than k:
- update the answer with the maximum of the previous answer and the current sum.
- increase the left pointer.
- Else Decrease the right pointer.
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find max sum less than k int maxSum(vector< int > arr, int k) { // Sort the array sort(arr.begin(), arr.end()); int n = arr.size(), l = 0, r = n - 1, ans = 0; // While l is less than r while (l < r) { if (arr[l] + arr[r] < k) { ans = max(ans, arr[l] + arr[r]); l++; } else { r--; } } return ans; } // Driver Code int main() { vector< int > A = { 20, 10, 30, 100, 110 }; int k = 85; // Function Call cout << maxSum(A, k) << endl; } |
Java
// Java program for the above approach import java.util.Arrays; class GFG { // Function to find max sum less than k static int maxSum( int arr[], int k) { // Sort the array Arrays.sort(arr); int n = arr.length, l = 0 , r = n - 1 , ans = 0 ; // While l is less than r while (l < r) { if (arr[l] + arr[r] < k) { ans = Math.max(ans, arr[l] + arr[r]); l++; } else { r--; } } return ans; } // Driver Code public static void main (String[] args) { int []A = { 20 , 10 , 30 , 100 , 110 }; int k = 85 ; // Function Call System.out.print(maxSum(A, k)); } } // This code is contributed by Aman Kumar. |
Python3
# Python program for above approach # Function to find max sum less than k def maxSum(arr, k): # Sort the array arr.sort() n,l = len (arr), 0 r,ans = n - 1 , 0 # While l is less than r while (l < r): if (arr[l] + arr[r] < k): ans = max (ans, arr[l] + arr[r]) l + = 1 else : r - = 1 return ans # Driver Code A = [ 20 , 10 , 30 , 100 , 110 ] k = 85 # Function Call print (maxSum(A, k)) # This code is contributed by shinjanpatra |
C#
// C# implementation of the approach using System; class GFG { // Function to find max sum less than k static int maxSum( int [] arr, int k) { // Sort the array Array.Sort(arr); int n = arr.Length, l = 0, r = n - 1, ans = 0; // While l is less than r while (l < r) { if (arr[l] + arr[r] < k) { ans = Math.Max(ans, arr[l] + arr[r]); l++; } else { r--; } } return ans; } // Driver code public static void Main () { int [] A = { 20, 10, 30, 100, 110 }; int k = 85; // Function Call Console.WriteLine(maxSum(A, k)); } } // This code is contributed by target_2. |
Javascript
<script> // Javascript program for the above approach // Function to find max sum less than k function maxSum(arr, k) { // Sort the array arr.sort((a,b)=>a-b); var n = arr.length, l = 0, r = n - 1, ans = 0; // While l is less than r while (l < r) { if (arr[l] + arr[r] < k) { ans = Math.max(ans, arr[l] + arr[r]); l++; } else { r--; } } return ans; } // Driver Code var A = [20, 10, 30, 100, 110]; var k = 85; // Function Call document.write( maxSum(A, k)); </script> |
50
Time complexity: O(NlogN)
Auxiliary Space: O(1)