In this HackerEarth Choose K Numbers problem solution, You are given an array Arri of size N. You have to find the maximum value of K such that after choosing K numbers from the array the DiffValue of chosen numbers is less than or equal to S.

DiffValue for a set of integers is defined as the largest possible difference among any two integers of the set. However if you choose K numbers from the array, value of all the chosen numbers get multiplied by K.

Hence print two integers i.e the largest value of number K and largest possible DiffValue corresponding to value of K.


HackerEarth Choose K Numbers problem solution


HackerEarth Choose K Numbers problem solution.

#include <bits/stdc++.h>
#define sflld(n) scanf("%lld",&n)
#define sfulld(n) scanf("%llu",&n)
#define sfd(n) scanf("%d",&n)
#define sfld(n) scanf("%ld",&n)
#define sfs(n) scanf("%s",&n)
#define ll long long
#define s(t) int t; while(t--)
#define ull unsigned long long int
#define pflld(n) printf("%lld\n",n)
#define pfd(n) printf("%d\n",n)
#define pfld(n) printf("%ld\n",n)
#define lt 2*idx
#define rt 2*idx+1
#define f(i,k,n) for(i=k;i<n;i++)
#define MAXN 100005
#define FD freopen("out.txt", "w", stdout);
#define FC fclose(stdout);

using namespace std;
int cost[MAXN],n,s,v[MAXN];
bool cal(int k)
{
int i;


f(i,0,n)
{
v[i]=(cost[i]*k);
}
bool fl=0;
f(i,0,n-k+1)
{
if(v[i+k-1]-v[i]<=s)
{
fl=1;
break;
}
}
return fl;
}
int main()
{
int t;
sfd(t);
while(t--)
{
int i,j;
sfd(n);
sfd(s);
f(i,0,n)
{
sfd(cost[i]);
}
sort(cost,cost+n);
int l=1,r=n;
int k;
while(l<=r)
{
ll m=(l+r)/2;
// cout<<l<<" "<<r<<" "<<m<<endl;
if(cal(m))
{
k=m;
l=m+1;
}
else
r=m-1;
}
int mx=-1;
f(i,0,n)
{
v[i]=(cost[i]*k);
}
f(i,0,n-k+1)
{
if(v[i+k-1]-v[i]<=s)
{
mx=max(mx,v[i+k-1]-v[i]);
}
}
cout<<k<<" "<<mx<<endl;
}


return 0;
}

Second solution

#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <math.h>
#include <string>

using namespace std;

#define maxN 50000
#define ll long long int

ll n,sum;
ll a[maxN+5];

bool valid(ll k)
{
ll i;
for(i=0;(i+k)<=n;i++)
if(((a[i+k-1]-a[i])*k)<=sum)
return true;
return false;
}

ll searchb(ll s,ll e)
{
ll m;
while((e-s)>1)
{
m=s+(e-s)/2;
if(valid(m))
s=m;
else
e=m-1;
}
if(valid(e))
return e;
if(valid(s))
return s;
return 0;
}

int main()
{
ll t,i,k,val;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&sum);
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
k=searchb(0,n);
val=0;
for(i=0;(i+k)<=n;i++)
if((a[i+k-1]-a[i])*k<=sum)
val=max(val,(a[i+k-1]-a[i])*k);
printf("%lld %lld\n",k,val);
}
return 0;
}