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