k | Java 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 ( ub + i + 1 ) from this position to count ; returns the upper bound ; Returns k - th absolute difference ; Sort array ; Minimum absolute difference ; Maximum absolute difference ; Do binary search for k - th absolute difference ; Driver function to check the above functions
import java . util . Scanner ; import java . util . Arrays ; class GFG { static int countPairs ( int [ ] a , int n , int mid ) { int res = 0 , value ; for ( int i = 0 ; i < n ; i ++ ) { int ub = upperbound ( a , n , a [ i ] + mid ) ; res += ( ub - ( i - 1 ) ) ; } return res ; } static int upperbound ( int a [ ] , int n , int value ) { int low = 0 ; int high = n ; while ( low < high ) { final int mid = ( low + high ) / 2 ; if ( value >= a [ mid ] ) low = mid + 1 ; else high = mid ; } return low ; } static int kthDiff ( int a [ ] , int n , int k ) { Arrays . sort ( a ) ; int low = a [ 1 ] - a [ 0 ] ; for ( int i = 1 ; i <= n - 2 ; ++ i ) low = Math . 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 ; } public static void main ( String args [ ] ) { Scanner s = new Scanner ( System . in ) ; int k = 3 ; int a [ ] = { 1 , 2 , 3 , 4 } ; int n = a . length ; System . out . println ( kthDiff ( a , n , k ) ) ; } }