HackerEarth Choose K Numbers problem solution

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.

#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("%lldn",n)
#define pfd(n) printf("%dn",n)
#define pfld(n) printf("%ldn",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 %lldn",k,val);
    }
    return 0;
}

coding problems solutions