In this HackerEarth Danny! problem solution You are given a sequence of positive integers in the form of an array A of size N and a number K. Now, you need to perform a certain procedure over this sequence that is as follows :
  1. For each pair (i,j), where 1 <= i < j <= N store in a list | A[i] - A[j] |
  2. Sort this list in non-decreasing order
  3. Print the Kth element of this list (1 indexed)

Note that X denotes the absolute value of any integer X

You need to perform the following procedure and print to output whatever it leads to. Can you do it ?



HackerEarth Danny ! problem solution


HackerEarth Danny! problem solution.

import java.io.*;
import java.util.*;
import java.math.*;

public final class solution
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static int n;
static long k;
static long[] a;

static void shuffle(long[] a)
{
for(int i=0;i<a.length;i++)
{
int next=rnd.nextInt(a.length);

long temp=a[i];a[i]=a[next];a[next]=temp;
}
}

static boolean check(long val)
{
long ret=0;

for(int i=1;i<n;i++)
{
int low=0,high=i;

while(low<high)
{
int mid=(low+high+1)>>1;

if(a[i]-a[i-mid]<=val)
{
low=mid;
}
else
{
high=mid-1;
}
}

if(a[i]-a[i-low]<=val) ret+=low;
}

return (ret>=k);
}

public static void main(String args[]) throws Exception
{
n=sc.nextInt();k=sc.nextLong();a=new long[n];

if(n<2 || n>200000) throw new Exception("Wrong!");

long now = (((long)n)*((long)n-1))/2;

if(k<1 || k>now)
{
throw new Exception("Wrong!");
}

for(int i=0;i<n;i++)
{
a[i]=sc.nextLong();

if(a[i]<1 || a[i]>(int)(1e9))
{
throw new Exception("Wrong!");
}
}

shuffle(a);Arrays.sort(a);

long low=0,high=(long)(1e9);

while(low<high)
{
long mid=(low+high)>>1;

if(check(mid))
{
high=mid;
}
else
{
low=mid+1;
}
}

out.println(low);out.close();
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}

Second solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1000000005;
long long int f(int diff, vector <int> &A)
{
long long int ret = 0;
for (int i = 0; i < A.size(); ++i)
{
vector <int>::iterator it = lower_bound(A.begin(), A.end(), A[i] - diff);
int pos = (it - A.begin());
ret+=(i - pos);
}
return ret;
}
int main()
{
int n;
long long int k;
cin>>n>>k;
vector <int> A(n);
for (int i = 0; i < n; ++i)
{
cin>>A[i];
}
sort(A.begin(), A.end());
int lo = 0, hi = INF, mid;
while(lo < hi)
{
mid = (lo + hi)/2;
if(f(mid,A) >= k)
hi = mid;
else
lo = mid + 1;
}
cout<<lo<<"\n";
return 0;
}