kth Smallest Difference - Solution

Problem : kth Smallest Difference

You are given an array of integers. Consider absolute difference between all the pairs of the the elements. You need to find Kthsmallest absolute difference.If the size of the array is N then value of K will be less than N and more than or equal to 1.
Kth Smallest Difference Contest

Note: All the differences between pairs are considered to be different.

Hint

Input:
First line of input contains number of testcases T. The 1st line of each testcase contains a two integers N and K denoting the number of elements in the array A  and difference you need to output. The 2nd line of each testcase, contains N space separated integers denoting the elements of the array A.

Output:
For each test case, Output Kth smallest absolute difference.

Constraints:
1<= T <= 102
2 <= N <= 105
1 <= K < N
0 <= A[i] <= 105

Example:
Input :
1
6 2
1 3 4 1 3 8
Output :
0

Explanation :
Testcase1: First smallest difference is 0 , between the pair (1,1) and second smallest absolute difference difference is also 0 between the pairs (3,3).

Solution:

#include <bits/stdc++.h>
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+1, 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 T ;
    cin>>T;
    while(T--){
        int n, k;
        cin>>n>>k;
        int a[n];
        for(int i=0; i<n; i++){
            cin>>a[i];
        }
        cout<<kthDiff(a,n,k)<<endl;
    }
    return 0;
}