Problem Link:
Author: Niket Agarwal
Tester: Pritish Priyatosh Nayak
Editorialist: Niket Agawal
Difficulty:
Cakewalk
Prerequisites:
Hash Table
Problem:
Given an array of integers. Find the minimum number of subsequences the array can be divided to such that no two subsequences contain the same element.
Explanation:
Count the frequency of each element given. Since the range of A[I] was below 1e6.
A simple hash table (frequency array) could be used to count.
The answer was the maximum frequency.
Solutions:
Setter's/Editorialist's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
int[]freq=new int[(int)1e6+1];
for(int i=0;i<n;i++)
freq[ni()]++;
Arrays.sort(freq);
pn(freq[(int)1e6]);
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t;
cin>>t;
assert(t>=1&&t<=1000);
int sumn=0;
while(t--)
{
int n;
cin>>n;
assert(n>=1&&n<=1000);
sumn+=n;
assert(sumn>=1&&sumn<=1000);
map<int,int> mpp;
for (int i = 0; i < n; ++i)
{
int x;
cin>>x;
assert(x<=1e6&&x>=1);
mpp[x]++;
}
int ans=0;
for(auto &[x,y]:mpp)
ans=max(ans,y);
cout<<ans<<'\n';
}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}