HackerEarth Fredo and Large Numbers problem solution

In this HackerEarth Fredo and Large Numbers problem solution Fredo is pretty good at dealing large numbers. So, once his friend Zeus gave him an array of N numbers , followed by Q queries which he has to answer. In each query , he defines the type of the query and the number f for which Fredo has to answer.

Each query is of the following two types:

Type 0: For this query, Fredo has to answer the first number in the array (starting from index 0) such that its frequency is atleast equal to f.

Type 1: For this query, Fredo has to answer the first number in the array such that frequecy is exactly equal to f.

Now, Fredo answers all his queries but now Zeus imagines how he should verify them . So, he asks you to write a code for the same.

HackerEarth Fredo and Large Numbers problem solution.

#include<bits/stdc++.h>
#define N 1000000
#define ll long long
using namespace std;
ll temp[N+5],arr[N+5],val[N+5];
int n,maxx=-1,freq[N+5],j,first[N+5],exact[N+5];
bool vis[N+5];
void compress()
{
    sort(temp,temp+n);
    for(int i=0;i<n;i++)
    {
        ll temp1=arr[i];
        arr[i]=lower_bound(temp,temp+n,arr[i])-temp+1;
        val[arr[i]]=temp1;
        freq[arr[i]]++;
        maxx=max(maxx,freq[arr[i]]);
    }
    int limit=0;
    for(int i=0;i<n;i++)
    {
        int maxf=freq[arr[i]];
        if(maxf>limit)
        {
            while(maxf-limit)
                first[maxf--]=arr[i];//val[arr[i]];
            limit=freq[arr[i]];
        }
        if(!vis[freq[arr[i]]])
        {
            exact[freq[arr[i]]]=arr[i];//val[arr[i]];
            vis[freq[arr[i]]]=1;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&arr[i]);
        temp[i]=arr[i];
    }
    compress();
    //cout<<maxx<<endl;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int type;
        ll f;
        scanf("%d%lld",&type,&f);
        if(f>maxx){printf("0n");continue;}
        switch(type)
        {
            case 0:
                printf("%lldn",val[first[f]]);
                break;
            case 1:
                printf("%lldn",val[exact[f]]);
                break;
        }
    }
    return 0;
}

HackerEarth Fredo and Large Numbers problem solution.

Leave a Reply