text: k | C ++ program to find k - th absolute difference between two elements ; returns number of pairs with absolute difference less than or equal to mid . ; Upper bound returns pointer to position of next higher number than a [ i ] + mid in a [ i . . n - 1 ] . We subtract ( a + i + 1 ) from this position to count ; Returns k - th absolute difference ; Sort array ; Minimum absolute difference ; Maximum absolute difference ; Do binary search for k - th absolute difference ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairs ( int * a , int n , int mid ) { int res = 0 ; for ( int i = 0 ; i < n ; ++ i ) res += upper_bound ( a + i , a + n , a [ i ] + mid ) - ( a + i + 1 ) ; return res ; } int kthDiff ( int a [ ] , int n , int k ) { sort ( a , a + n ) ; int low = a [ 1 ] - a [ 0 ] ; for ( int i = 1 ; i <= n - 2 ; ++ i ) low = min ( low , a [ i + 1 ] - a [ i ] ) ; int high = a [ n - 1 ] - a [ 0 ] ; while ( low < high ) { int mid = ( low + high ) >> 1 ; if ( countPairs ( a , n , mid ) < k ) low = mid + 1 ; else high = mid ; } return low ; } int main ( ) { int k = 3 ; int a [ ] = { 1 , 2 , 3 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << kthDiff ( a , n , k ) ; return 0 ; }