Given an array of integers arr[] of size N and an integer K, the task is to find the K-th smallest pair sum of the given array.
Examples:
Input: arr[] = {1, 5, 6, 3, 2}, K = 3
Output: 5
Explanation: The sum of all the pairs are: 1+5 = 6, 1+6 = 7, 1+3 = 4, 1+2 = 3, 5+6 = 11, 5+3 = 8, 5+2 = 7, 6+3 = 9, 6+2 = 8, 2+3 = 5. The 3rd smallest among these is 5.Input: arr[] = {2, 4, 5, 6}, K = 6
Output: 11
Naive Approach: This is a greedy approach. We will get the sums of all possible pairs and store them in an array. Then we will sort that array in ascending order and the K-th value is the required answer.
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to get the Kth smallest pair sumint kthPairSum(vector<int>& arr, int K){ int n = arr.size(); // Vector to store the sums vector<int> v; // Iterating to get the sums of all // possible pairs and store them for(int i=0;i<n;i++) { for (int j=i+1; j<n; j++) { v.push_back(arr[i]+arr[j]); } } // Sorting the new vector sort(v.begin(),v.end()); // Returning kth element return v[K-1];}// Driver codeint main(){ vector<int> arr = { 1, 5, 6, 3, 2 }; int K = 3; cout << kthPairSum(arr, K); return 0;}// This code is contributed by Utkarsh. |
Java
import java.util.*;public class Main { // Function to get the Kth smallest pair sum static int kthPairSum(List<Integer> arr, int K) { int n = arr.size(); // Vector to store the sums List<Integer> v = new ArrayList<>(); // Iterating to get the sums of all // possible pairs and store them for(int i=0;i<n;i++) { for (int j=i+1; j<n; j++) { v.add(arr.get(i) + arr.get(j)); } } // Sorting the new vector Collections.sort(v); // Returning kth element return v.get(K-1); } // Driver code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(Arrays.asList(1, 5, 6, 3, 2)); int K = 3; System.out.println(kthPairSum(arr, K)); }} |
Python3
# Python code for above approach# Function to get the Kth smallest pair sumdef kthPairSum(arr, K): n = len(arr) # Vector to store the sums v = [] # Iterating to get the sums # of all possible pairs and store them for i in range(0, n): for j in range(i + 1, n): v.append(arr[i] + arr[j]) # Sorting the new vector v.sort() # Returning kth element return v[K - 1] # Driver code arr = [1, 5, 6, 3, 2] K = 3 print(kthPairSum(arr, K)) |
C#
// C# code addition using System;using System.Collections.Generic;using System.Linq;public class Program{ // Function to get the Kth smallest pair sum public static int KthPairSum(List<int> arr, int K) { int n = arr.Count; // List to store the sums List<int> v = new List<int>(); // Iterating to get the sums of all // possible pairs and store them for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { v.Add(arr[i] + arr[j]); } } // Sorting the new list v.Sort(); // Returning kth element return v[K - 1]; } // Driver code public static void Main() { List<int> arr = new List<int> { 1, 5, 6, 3, 2 }; int K = 3; Console.WriteLine(KthPairSum(arr, K)); }}// The code is contributed by Arushi Goel. |
Javascript
// javascript code for above approach// Function to get the Kth smallest pair sumfunction kthPairSum(arr, K){ let n = arr.length; // Vector to store the sums let v = []; // Iterating to get the sums of all // possible pairs and store them for(let i=0;i<n;i++) { for (let j=i+1; j<n; j++) { v.push(arr[i]+arr[j]); } } // Sorting the new vector v.sort(); // Returning kth element return v[K-1]+1;}// Driver codelet arr = [ 1, 5, 6, 3, 2 ];let K = 3;console.log(kthPairSum(arr, K));// This code is contributed by Arushi Jindal. |
Output
5
Time Complexity: O (N2 * log(N2))
Auxiliary Space: O(N2)
Efficient Approach: The concept of this approach is based on max-heap. We will be implementing a max heap of size K. Follow the steps mentioned below:
- Start iterating the array from i = 0 to i = N-2.
- For every i iterate from j = i+1 to j = N-1.
- Get the sum of this (i, j) pair and insert it in the max heap.
- If the heap is full then compare the top element of the heap with this sum.
- If the value of the top element is greater then replace that with the new sum.
- When the iteration is over the topmost element of the max-heap is the K-th smallest pair sum.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to get the Kth smallest pair sumint kthPairSum(vector<int>& arr, int K){ int n = arr.size(); // Priority queue to implement max-heap priority_queue<int> pq; // Loop to calculate all possible pair sum for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Variable to store the sum int temp = arr[i] + arr[j]; // If the heap is full if (pq.size() == K) { // If the top element is greater if (pq.top() > temp) { pq.pop(); pq.push(temp); } } else pq.push(temp); } } // Return the Kth smallest value return pq.top();}// Driver codeint main(){ vector<int> arr = { 1, 5, 6, 3, 2 }; int K = 3; cout << kthPairSum(arr, K); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { // Function to get the Kth smallest pair sum static int kthPairSum(int[] arr, int K) { int n = arr.length; // Priority queue to implement max-heap // Creating empty priority queue PriorityQueue<Integer> pq = new PriorityQueue<Integer>( Collections.reverseOrder()); // Loop to calculate all possible pair sum for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Variable to store the sum int temp = arr[i] + arr[j]; // If the heap is full if (pq.size() == K) { // If the top element is greater if (pq.peek() > temp) { pq.poll(); pq.add(temp); } } else pq.add(temp); } } // Return the Kth smallest value return pq.peek(); } // Driver code public static void main(String[] args) { int[] arr = { 1, 5, 6, 3, 2 }; int K = 3; System.out.println(kthPairSum(arr, K)); }}// This code is contributed by Potta Lokesh |
Python3
from queue import PriorityQueue# Function to get the Kth smallest pair sumdef kthPairSum(arr, K): n = len(arr); # Priority queue to implement max-heap pq = PriorityQueue() # Loop to calculate all possible pair sum for i in range(n - 1): for j in range(i + 1, n): # Variable to store the sum temp = arr[i] + arr[j]; # If the heap is full if (pq.qsize() == K): # If the top element is greater if (pq.queue[-1] > temp): pq.get(); pq.put(temp); else: pq.put(temp); # Return the Kth smallest value return pq.queue[0];# Driver codearr = [ 1, 5, 6, 3, 2 ];K = 3;print(kthPairSum(arr, K));# This code is contributed by saurabh_jaiswal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to get the Kth smallest pair sum static int kthPairSum(int[] arr, int K) { int n = arr.Length; // Priority queue to implement max-heap // Creating empty priority queue List<int> pq = new List<int>(); // Loop to calculate all possible pair sum for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Variable to store the sum int temp = arr[i] + arr[j]; // If the heap is full if (pq.Count == K) { // If the top element is greater if (pq[0] > temp) { pq.Remove(0); pq.Add(temp); } } else pq.Add(temp); } } // Return the Kth smallest value return pq[0]-1; }// Driver Codepublic static void Main(){ int[] arr = { 1, 5, 6, 3, 2 }; int K = 3; Console.Write(kthPairSum(arr, K));}}// This code is contributed by avijitmondal1998. |
Javascript
<script>// Javascript code for the above approach// Function to get the Kth smallest pair sumfunction kthPairSum(arr, K){ let n = arr.length; // Priority queue to implement max-heap pq = []; // Loop to calculate all possible pair sum for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { // Variable to store the sum let temp = arr[i] + arr[j]; // If the heap is full if (pq.length == K) { // If the top element is greater if (pq[0] > temp) { pq.shift(); pq.push(temp); pq.sort((a, b) => b - a); } } else {pq.push(temp); pq.sort((a, b) => b - a);} } } // Return the Kth smallest value return pq[0];}// Driver code let arr = [ 1, 5, 6, 3, 2 ]; let K = 3; document.write(kthPairSum(arr, K));// This code is contributed by Pushpesh raj</script> |
Output
5
Time Complexity: O(N2 * logK)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
