MAXCOUNT - Editorial

admin · November 22, 2012, 1:42pm

PROBLEM LINKS

DIFFICULTY

EASY

EXPLANATION

This was supposed to be a problem that anyone who knows basic programming could solve and I’m glad that it’s satisfied our expectations.

For the given constraints there were two easy approaches that one could use to solve this problem:

Approach 1:
The number of elements in the array bounded just by 100. For each element check how many other elements are equal to this one and hence find out what is the corresponding count. This would take time O(N²). Since N <= 100 here this solution would fit easily into the time limit.

Approach 2:
The range of elements is small - all elements are between 1 and 10000. One could create a frequency map for the array. I.e. create an array FREQ of size 10000 such that FREQ_[x] gives the number of times the number x appears in the array. Initially all values in FREQ are zeros. When you start reading input and say you read a number x, you should add 1 to FREQ_[x]. It takes O(N) time to build this array after initialization. When all input values have been scanned, one could make iteration at the FREQ array to find the smallest element with the largest count.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

cybercam · March 2, 2013, 6:24am

from collections import Counter
def com(N,A):
num_array=A.split()
c=Counter(num_array)
C=max(c.values())
l1=[]
for k in c:
if c[k]==C:
l1.append(k)

    V1=min(l1)
    V=int(V1)
    print V,C

t=input()
for i in range(t):
    N=input()
    A=raw_input()
    com(N,A)

What’s wrong with this??

code_billmark · August 18, 2013, 11:26am

instead of hashing i just used bubble sort technique, works well on your test cases…!! why does it give wrong ans. here…!!
plz check my code
/*count of maximum
MAXCOUNT
*/

#include<stdio.h>
int main()
{
int t,k,n,swap,maxfreq,freq,no,nomax,i,j;
scanf("%d",&t);

for(i=0;i<t;i++)
{
scanf("%d",&n);
int arr[n];

for(j=0;j<n;j++)
scanf("%d",&arr[j]);

for(j=0;j<n-1;j++)
{

for(k=0;k<n-j-1;k++)
{

if(arr[k]>arr[k+1])
{
swap=arr[k];
arr[k]=arr[k+1];
arr[k+1]=swap;
}
}
}

maxfreq=1;nomax=arr[0];freq=1;no=arr[0];
for(j=1;j<n;j++)
{

if(arr[j]==no)
{
freq++;
continue;
}
else if(freq>maxfreq)
{
maxfreq=freq;
nomax=arr[j-1];
}
freq=1;
no=arr[j];
}

printf("%d %d\n",nomax,maxfreq);
}

return 0;
}

dhee25khatri · October 11, 2013, 7:41pm

why it is giving wrong answer?

#include <iostream>
#include <map>
using namespace std;

map<char,long int>mymap;
map<char,long int>::iterator it;

void maxcount(){
    long long int occr=mymap.begin()->second;
    char num=mymap.begin()->first;
    for(it=mymap.begin();it!=mymap.end();it++){
        if(it->second > occr){
            occr=it->second;
            num=it->first;
        }
    }
cout<<num<<"  "<<occr<<endl;
mymap.clear();
}

void intialize(long long int len){
    char a;
    while(len--){
        cin>>a;
        it=mymap.find(a);
        if(it!=mymap.end()) it -> second++;
        else mymap[a]=1;
    }
maxcount();
}


int main()
{
    long long int tc,len;
    cin>>tc;
    while(tc--){
        cin>>len;
        intialize(len);
    }
    return 0;
}

dhee25khatri · October 11, 2013, 7:52pm

what is wrong in this code i have tried too much but getting wrong answer but for my inputs i am getting right!
link is http://www.codechef.com/viewsolution/2808030

dhee25khatri · October 11, 2013, 7:53pm

#include
#include
using namespace std;

map<char,long int>mymap;
map<char,long int>::iterator it;
 
void maxcount(){
long long int occr=mymap.begin()->second;
char num=mymap.begin()->first;
for(it=mymap.begin();it!=mymap.end();it++){
if(it->second > occr){
occr=it->second;
num=it->first;
}
}
cout<<num<<" "<<occr<<endl;
mymap.clear();
}
 
void intialize(long long int len){
char a;
while(len--){
cin>>a;
it=mymap.find(a);
if(it!=mymap.end()) it -> second++;
else mymap[a]=1;
}
maxcount();
}
 
 
int main()
{
long long int tc,len;
cin>>tc;
while(tc--){
cin>>len;
intialize(len);
}
return 0;
}

shubham12 · December 2, 2013, 10:39pm

instead of scanning FREQ later wouldn’t it be better to keep a record of current v & c and keep updating it,while taking the input?

jam343 · February 8, 2014, 3:07am

#include
using namespace std;
#include<bits/stdc++.h>
bool compare(const int &a,const int &b)
{
return a<b;
}
int main(){
int arr[103],n,t,i;
int p=0,m,k=0;
cin>>t;
while(t–){
cin>>n;
for(i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n,compare);
for(i=0;i<n;i++){
int count=0;
int j;
m=p;
for(j=0;j<n;j++){
if(arr[i]==arr[j])
count+=1;
}
if(k<count){
k=count;
p=arr[i];
}
else if(k==count) {
if(m>p)
p=m;
}
else
continue;
}
cout<<p;
printf(" “);
cout<<k;
printf(”\n");
}
return 0;
}what is the arror in this plesase tell me

mrigank · March 29, 2014, 8:18am

I have gone through many test cases,yet I think I might be missing some special case or am making some silly mistake. Can anyone please help me out with the wrong answer…?? Here is my code in C:-

#include<stdio.h>
int main()
{
long int t,n,max=0,k,l,i,nummax=0,num;
scanf("%ld",&t);
if (t < 1 || t > 100)
return -1;
while(t–)
{
scanf("%ld",&n);
// nummax=0,max=0,k=0,l=0,i=1;
if (n < 1 || n > 100)
return -1;
long int arr[10000]={0};
for(i=1;i<=n;i++)
{
scanf("%ld",&num);
if (num < 1 && num > 10000)
return -1;
if (num>nummax)
nummax=num;
arr[num]=arr[num]+1;
}
/*for(i=1;i<=n;i++)
printf("%ld",arr[i]);
*/
max=arr[1];
k=1;
for(i=1;i<=nummax;i++)
{
if (arr[i+1]>max)
{
max=arr[i+1];
k=i+1;
}
else if (arr[i+1]==max)
{
max=arr[i+1];
l=i+1;
}
}
//printf("%ld %ld\n",k,l);
if (arr[k]==max && arr[l]==max)
{
if (k>l)
printf("%ld %ld\n",l,arr[l]);
else
printf("%ld %ld\n",k,arr[k]);
}
else
printf("%ld %ld\n",k,arr[k]);
}
return 0;
}

nickzuck_007 · October 16, 2014, 10:13pm

Can’t we do it in a way that one can sort the array and then find the corresponding count of the elements and if the two counts were same the lesser will be taken if we move from right to the left (assuming sorting in ascending order )

akshit_96 · February 23, 2015, 9:33am

#include<stdio.h>
int main()
{
int max,i,t,n,num,freq[10001],a[101];
scanf("%d",&t);
while(t)
{
for(i=0;i<10001;i++)
freq[i]=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
freq[a[i]]++;
}
max=freq[0];
for(i=0;i<10001;i++)
{
if(freq[a[i]]>max)
{ max=freq[a[i]];
num=a[i];}
}
printf("%d %d\n",num,max);
t–;
}
return 0;
}

darsh003 · May 28, 2015, 4:32pm

really not getting what am i doing wrong help me here is my code

#include
#include
using namespace std;

int ar[101]= {0};
int main() {

int t,x,y,p;
int count;
int max=0;
cin>>p;
while(p--){
cin>>t;

for(int i= 0;i<t;i++)
cin>> ar[i];
sort(ar,ar+t);
for(int j= 0;j<t;j++)		
{	count =0;
	x=ar[j];
	for(int k=j;k<t;k++)
	{
		if(ar[k]==x)
		count++;
		else if(ar[k]>x)
		break;
		
	}

 if(count>max)
	{max = count;
	y=x;}
	
}
cout<<y<<" "<<max<<"\n";
}
return 0;

}

write2diba · June 13, 2015, 11:30pm

Is there any test case which can definitely give me an idea whether I have done correctly or not. The test cases given in the problem is smoothly run by my program whereas when I submit it in codechef it shows wrong answer. i don’t even understand what’s the problem with my code. Please help me out.

gmahadevan89 · November 2, 2015, 10:08pm

Heh guys did someone manage to submit the solution using maps? If yes, can you post the link to your solution?

katpawan · December 30, 2015, 4:48pm

//-------------------------MAXCOUNT-----------------------------------------//
#include <stdio.h>

int main(void)
{
int test_case;
int size;
int array[100];

int target1,target2;
int count1=1,count2=0;

int i,j,swap;
scanf("%d",&test_case);

while(test_case--)
{
     scanf("%d",&size);
     
     for(i=0;i<size;i++)
        scanf("%d",&array[i]);
        
       for(i=0;i<(size-1);i++)
       {
           for(j=0;j<(size-i-1);j++)
           {
               if(array[j]>array[j+1])
               {
                   swap       = array[j];
                   array[j]   = array[j+1];
                   array[j+1] = swap;
               }
           }
       }
       
  /*     printf("sorted--\n");
       for(i=0;i<size;i++)
         printf("%d\t",array[i]); */
       
       target1=array[0];
       for(j=1;j<size;j++)
       {
          if(array[j]==target1)
             count1++;
          else
          {
             
             if(count1>count2)
             {
                 count2=count1;
                 
                 target2=target1;
             }
             target1=array[j];
             count1=1;
              
          }
             
       }
     
     if(count1>count2)
       printf("%d %d\n",target1,count1);
     else
    printf("%d %d\n",target2,count2);
}
return 0;

}
WHAT IS THE PROBLEM WITH ABOVE CODE???

dusht1408 · January 23, 2016, 5:11pm

/*
To count the frequency of a number with O(n) complexity.

Algorithm:
1.Take Input Array of size n.
cin>>a[i]
2.Sort the array with nlogn complexity.
sort(a,a+n)
3.Create a new array and fill it’s elements with 1
c[i]=1
4.initialize x as -1 and y as 1
5.run a loop from starting index 0 to n.
for i=0 to i<n
6.if x is equal to a[i] then y++ and c[i]=y
where c[i] denotes the number of times a[i] has appeared
7.else y=1
if numbers changed then reset y=1
8.x=a[i] storing the previous number
9.create a copy of c[n] as b[n]
10.sort the array c[n]
11.find the b where c was maximum which will tell us the index with most frequency and use break for the minimum number with highest frequency.
for(i=0;i<n;i++)
if(b[i]==c[n-1]){
cnum=c[n-1]
num=a[i]
break;}
12.print cnum and num

*/

#include<stdio.h>
#include
#include
using namespace std;
main()
{
int t;
scanf("%d",&t);
while(t–)
{
int i,j,n;
cin>>n;
int a[n];
int c[n];
int x=-1,y=1;
for(i=0;i<n;i++)
c[i]=1;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
if(x==a[i]){
y++;
c[i]=y;}
else
y=1;

x=a[i];
}
int b[n],num,cnum;
for(i=0;i<n;i++)
b[i]=c[i];
sort(c,c+n);
for(i=0;i<n;i++)
{
if(c[n-1]==b[i])
{
num=a[i];
cnum=c[n-1];
break;
}
}
cout<<num<<" “<<cnum<<”\n";
}
}