In this HackerEarth Random Generator problem solution Aparna recently created a random number generator and now she wants Harsh to check if it works fine. She gives Harsh an array containing N numbers generated from this random number generator of hers, and two integers K and P. If the given array contains more than or equal to K numbers in the range X-P to X+P (both inclusive) for any integer X, then the random generator fails.

If for any X the generator fails then ultimately it fails.

Help Harsh in determining whether the random generator works well or not.


HackerEarth Random Generator problem solution


HackerEarth Random Generator problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define total 5000005
#define M 1000000000001
#define NIL 0
#define MAXN 200001
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;
vector<int>v;
int main(){
int t,n,i,k,p,j;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>t;
while(t--){
cin>>n>>k>>p;
for(i=0;i<n;i++){
cin>>j;
v.pb(j);
}
sort(all(v));
for(i=0;i<n;i++){
int id1=lower_bound(all(v),v[i]-2*p)-v.begin();
if(i-id1+1>=k){
cout<<"NO"<<endl;
break;
}
}
if(i==n)
cout<<"YES"<<endl;
v.clear();
}

fclose(stdout);

return 0;
}

Second solution

#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

#define MAXN 100000
#define MAXI 1000000000

vector<int> inp;
vector<int>::iterator up;
int T, N, K, P;

bool solve(){
int disp = 2*P ;
sort(inp.begin(), inp.end());

for(int i=0;i<N;i++){
int val = inp[i];
val = val+disp;
up = upper_bound(inp.begin(), inp.end(), val);
int idx = (up - inp.begin());
if (idx-i>=K)
return false;
}

return true;
}

int main(){
int a;
scanf("%d", &T);
assert(T>0);
assert(T<=10);

while(T--){
inp.clear();

scanf("%d %d %d", &N, &K, &P);
assert(N>0);
assert(N<=MAXN);
assert(K>0);
assert(K<=MAXN);
assert(P>=0);
assert(P<=MAXI);

for(int i=0;i<N;i++){
scanf("%d", &a);
assert(a>=-MAXI);
assert(a<=MAXI);
inp.push_back(a);
}
if(solve())
printf("YES\n");
else
printf("NO\n");
}
}