HackerEarth Danny ! problem solution

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.

`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;}`