Given an array arr[] containing N integers and a number K, the task is to find the K-th pair in the ordered list of all possible N2 sorted pairs of the array arr[].
A pair (p1, q1) is lexicographically smaller than the pair (p2, q2) only if p1 ? p2 and q1 < q2.
Examples:
Input: arr[] = {2, 1}, K = 4
Output: {2, 2}
Explanation:
The sorted sequence for the given array is {1, 1}, {1, 2}, {2, 1}, {2, 2}. So the 4th pair is {2, 2}.
Input: arr[] = {3, 1, 5}, K = 2
Output: {1, 3}
Approach: Naturally, K-th sorted pair from all possible set of pairs will be {arr[K/N], arr[K%N]}. But, this method works only if all the elements in the array are unique. Therefore, the following steps are followed to make the array behave like a unique array:
- Let the array arr[] be {X, X, X, … D1, D2, D3 … DN – T}.
- Here, let’s assume the number of repeating elements in the array to be T and the element which is being repeated be X. So, the number of distinct elements in the array is (N – T).
- Now, from the first N * T pairs out of N2 pairs of elements, the first T2 elements will always be {X, X}.
- The next T elements will be {X, D2} and the next T elements will be {X, D2} and so on.
- So, if we need to find the K-th element, subtract N * T from K and skip the first T same elements.
- Repeat the above process until K becomes less than N * T.
- At this step, the first element in the pair would be the counter variable ‘i’. The second element would be the remaining K-th element from the remaining elements which is K / T. So, the required answer is {arr[i], arr[K/T]}.
Below is the implementation of the above approach:
C++
// C++ program to find the K-th pair // in a lexicographically sorted array #include <bits/stdc++.h> using namespace std; // Function to find the k-th pair void kthpair( int n, int k, int arr[]) { int i, t; // Sorting the array sort(arr, arr + n); --k; // Iterating through the array for (i = 0; i < n; i += t) { // Finding the number of same elements for (t = 1; arr[i] == arr[i + t]; ++t) ; // Checking if N*T is less than the // remaining K. If it is, then arr[i] // is the first element in the required // pair if (t * n > k) break ; k = k - t * n; } // Printing the K-th pair cout << arr[i] << ' ' << arr[k / t]; } // Driver code int main() { int n = 3, k = 2; int arr[n] = { 3, 1, 5 }; kthpair(n, k, arr); } |
Java
// Java program to find the K-th pair // in a lexicographically sorted array import java.util.*; class GFG{ // Function to find the k-th pair static void kthpair( int n, int k, int arr[]) { int i, t = 0 ; // Sorting the array Arrays.sort(arr); --k; // Iterating through the array for (i = 0 ; i < n; i += t) { // Finding the number of same elements for (t = 1 ; arr[i] == arr[i + t]; ++t) ; // Checking if N*T is less than the // remaining K. If it is, then arr[i] // is the first element in the required // pair if (t * n > k) break ; k = k - t * n; } // Printing the K-th pair System.out.print(arr[i] + " " + arr[k / t]); } // Driver code public static void main(String[] args) { int n = 3 , k = 2 ; int arr[] = { 3 , 1 , 5 }; kthpair(n, k, arr); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the K-th pair # in a lexicographically sorted array # Function to find the k-th pair def kthpair(n, k, arr): # Sorting the array arr.sort() k - = 1 # Iterating through the array i = 0 while (i < n): # Finding the number of same elements t = 1 while (arr[i] = = arr[i + t]): t + = 1 # Checking if N*T is less than the # remaining K. If it is, then arr[i] # is the first element in the required # pair if (t * n > k): break k = k - t * n i + = t # Printing the K-th pair print (arr[i], " " , arr[k / / t]) # Driver code if __name__ = = "__main__" : n, k = 3 , 2 arr = [ 3 , 1 , 5 ] kthpair(n, k, arr) # This code is contributed by chitranayal |
C#
// C# program to find the K-th pair // in a lexicographically sorted array using System; class GFG{ // Function to find the k-th pair static void kthpair( int n, int k, int [] arr) { int i, t = 0; // Sorting the array Array.Sort(arr); --k; // Iterating through the array for (i = 0; i < n; i += t) { // Finding the number of same elements for (t = 1; arr[i] == arr[i + t]; ++t); // Checking if N*T is less than the // remaining K. If it is, then arr[i] // is the first element in the required // pair if (t * n > k) break ; k = k - t * n; } // Printing the K-th pair Console.Write(arr[i] + " " + arr[k / t]); } // Driver code static public void Main () { int n = 3, k = 2; int [] arr = { 3, 1, 5 }; kthpair(n, k, arr); } } // This code is contributed by ShubhamCoder |
Javascript
<script> // Java program to find the K-th pair // in a lexicographically sorted array // Function to find the k-th pair function kthpair(n,k,arr) { let i, t = 0; // Sorting the array arr.sort(); --k; // Iterating through the array for (i = 0; i < n; i += t) { // Finding the number of same elements for (t = 1; arr[i] == arr[i + t]; ++t) ; // Checking if N*T is less than the // remaining K. If it is, then arr[i] // is the first element in the required // pair if (t * n > k) break ; k = k - t * n; } // Printing the K-th pair document.write(arr[i] + " " + arr[k / t]); } // Driver code let n = 3, k = 2; let arr =[ 3, 1, 5 ]; kthpair(n, k, arr); //contributed by 171fa07058 </script> |
1 3
Time Complexity: O(N * log(N)), where N is the size of the array.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!