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.
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:
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.