[Solved] Kth Smallest Difference Contest Problem

You are given an array of integers. Consider absolute difference between all the pairs of the the elements. You need to find K^thsmallest 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.

Input:
First line of input contains number of testcases T. The 1^st 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 2^nd line of each testcase, contains N space separated integers denoting the elements of the array A.

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

Constraints:
1<= T <= 10²
2 <= N <= 10⁵
1 <= K < N
0 <= A[i] <= 10⁵

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:

import java.util.*;
import java.io.*;
import java.lang.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int arr[] = new int[n];
            for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

            System.out.println(Math.abs(small(arr, k)));
        }
    }

    static int small(int arr[], int k) {
        Arrays.sort(arr);
        int l = 0, r = arr[arr.length - 1] - arr[0];
        while (r > l) {
            int mid = l + (r - l) / 2;
            if (count(arr, mid) < k) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r;
    }

    static int count(int arr[], int mid) {
        int ans = 0, j = 0;
        for (int i = 1; i < arr.length; ++i) {
            while (j < i && arr[i] - arr[j] > mid) {
                ++j;
            }
            ans += i - j;
        }
        return ans;
    }
}

#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+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 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;
}

import atexit
import io
import sys

# Contributed by : Nagendra Jha

def count(a,mid):
    ans=0
    j=0
    for i in range(1,len(a)):
        while(j<i and a[i]-a[j] > mid):
            j+=1
        ans+=i-j

    return ans

def small(a,k):
    a.sort()
    l,r=0,a[len(a)-1]-a[0]

    while(r>l):
        mid = (l+r)//2
        if(count(a,mid)<k):
            l=mid+1
        else:
            r = mid
    return r

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        n,k = map(int,input().strip().split())
        a = list(map(int,input().strip().split()))
        print(small(a,k))

Happy Learning – If you require any further information, feel free to contact me.