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 :

For each pair (i,j), where 1 <= i < j <= N store in a list | A[i] – A[j] |
Sort this list in non-decreasing order
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;
}

coding problems solutions