REMOVEBAD Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Abhinav Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra

DIFFICULTY:

1100

PREREQUISITES:

None

PROBLEM:

Chef has an array A of length N.

In one operation, Chef can remove any one element from the array.

Determine the minimum number of operations required to make all the elements same.

EXPLANATION:

In order to make all the elements same, we will select the element with the maximum frequency and delete all the other elements. Thus we will calculate the frequency of each element and select the element say x with maximum frequency, say f. Then our answer would be:

n - f

where n is the size of the array.

In case there are more than element having same maximum frequency then we can select any one of them and our answer would still be the same.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like

actually m a beginner and trying to solve this qstn but getting tle someone please suggest how to deal with it without using maps or sets or any idea to reduce T.C of my code

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{ float t1,t2;
int n,count=0;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}int max=0;
for(int i=0;i<n;i++)
{ count=1;
for(int j=i+1;j<n;j++)
{
if(a[j]==a[i]){count++;}
}
if(count>max){max=count;}
}
cout<<n-max<<endl;

}

}