In this HackerEarth Highest Rating problem solution, Neha and Jenish are good friends. Neha challenges Jenish to find the Highest possible Rating of given array A after applying some queries. According to Neha, the Rating of an array is the highest occurrence of an element in the given array. Jenish is provided with the Magical Numbers M and Q. For Each element in the given Array A, Jenish can Perform Addition or Subtraction with M almost Q times.

Since Jenish is so confused and not able to come out with the solution, Help him to find the Highest Ratings Possible for Given Array after applying queries to each element.


HackerEarth Highest Rating problem solution


HackerEarth Highest Rating problem solution.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

import static java.lang.System.out;
/*
*  @author Nikunj Khokhar
*/
class Main {
    public static final int MIN_M = 1;
    public static final int MAX_M = 100;
    public static final int MIN_N = 1;
    public static final int MAX_N = 1000000;
    public static final int MIN_Ai = 1;
    public static final int MAX_Ai = 1000000;
    public static final int MIN_Q = 1;
    public static final int MAX_Q = 10;
    public static final BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String as[]) throws IOException {

        String temps[];
        int M = Integer.parseInt(br.readLine());
        int Q = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        int Ai;
        int highest_rating = 0, temp_rating;
        assert ((M >= MIN_M && M <= MAX_M) && (Q >= MIN_Q && Q <= MAX_Q) && (N >= MIN_N && N <= MAX_N)) : " Constraints Violated ";
        int hashArray[] = new int[MAX_Ai + 1];
        temps=br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            Ai = Integer.parseInt(temps[i]);
            assert (Ai >= MIN_Ai && Ai <= MAX_Ai) : " Constraints Violated ";
            hashArray[Ai]++;
        }
        for (int i = 1; i <= MAX_Ai; i++) {
            temp_rating = hashArray[i];
            for (int j = 0, k = i+M, l = i-M; j < Q; j++, k += M, l -= M) {
                if (k <= MAX_Ai) temp_rating += hashArray[k];
                if (l >= MIN_Ai) temp_rating += hashArray[l];
            }
            if (temp_rating >= highest_rating) highest_rating = temp_rating;
        }
        out.println(highest_rating);


    }

}

Second solution

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class highest_rating
{
    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 maxn=(int)(1e6+5);
    
    public static void main(String args[]) throws Exception
    {
        int m=sc.nextInt(),q=sc.nextInt(),n=sc.nextInt();int[] a=new int[n];
        
        int[] cnt=new int[maxn];
        
        if(m<1 || m>100 || q<1 || q>10 || n<1 || n>1000000)
        {
            throw new Exception("Wrong");
        }
        
        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
            
            if(a[i]<1 || a[i]>1000000)
            {
                throw new Exception("Wrong");
            }
            
            cnt[a[i]]++;
        }
        
        int max=0;
        
        for(int i=1;i<maxn;i++)
        {
            int curr=i,now=0,val=q;
            
            while(curr>=1 && val>=0)
            {
                now=now+cnt[curr];
                
                curr-=m;val--;
            }
            
            curr=i;val=q;
            
            while(curr<maxn && val>=0)
            {
                now=now+cnt[curr];
                
                curr+=m;val--;
            }
            
            max=Math.max(max,now-cnt[i]);
        }
        
        out.println(max);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());
    }
}