This blog will give you a clear picture why I used modulo.
Your code definitely doesn’t pass all testcases correctly - I even gave you an example case where it fails above.
As for the blog you linked, the first line says
Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k \leq n
k\leq n is important because that isn’t true in this problem - if you look at the constraints you’ll notice that here, k is 10^9.
The latter part of the editorial mentions several ways to count the frequencies of elements of an array which doesn’t depend on how big or small the elements themselves are at all, please try using one of those instead.
How can you say it is not true here ?
Because the problem statement says that 1\leq A_i\leq 10^9 and not 0\leq A_i < n.
The blog states that the array contains elements from 0 to k-1. Would you not agree then that k should be 10^9 + 1 here?
Give me any test case where it fails
I already did that above.
1
3
1 4 7
The answer is 1, not 0 (which is what your code outputs).
1 Like
Thank you. I got it
But there is no other way to count frequency except using hash map in C++ regarding this question ?
You can use a hashmap, you can use a normal (ordered) map, you can even sort the array and iterate over it or use binary search.
Acc to your logic, if the answer is less than N-2, all elements must be equal…
so cant the number be like this
2 6 2 6 2 6
here there is no need to delete any element
please guide if i am wrong!
It is needed to be deleted because 6-2 = 4. 2-2 =0 are not equal.
Take the first and second element: |2-6| = 4
Take the first and third element: |2-2| = 0
4 isn’t equal to 0.
1 Like
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define inf (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define goog(tno) cout << “Case #” << tno <<": "
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define w(t) int t; cin>>t ; while(t–)
using namespace std;
void gshikhar84(){
fast_io;
}
int main() {
gshikhar84();
w(t){
ll int n;
cin>>n;
ll int arr[n];
for(ll int i = 0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr , arr + n);
ll int count = 1;
ll int mx = INT_MIN;
for(ll int i = 0 ; i<n-1 ; i++){
if(arr[i] == arr[i+1]){
count++;
}
else{
mx = max(mx , count);
count = 1;
}
}
ll int ans;
if(mx == 1 && n > 1){
ans = n - 2;
}
else if(n == 1){
ans = 0;
}
else{
ans = n - mx;
}
cout<<ans<<endl;
}
return 0;
}
Can u plzz help me in finding my mistake. What I did is I simply sort the array now count the frequency of element with maximum frequency but if (n==1) print 0 , if count of maximum frequency = 1 and n > 1 print(n -2)…else i have printed n - mx where mx = frequency of max element.
You forgot to consider the frequency of the largest element of the array - that needs to be outside the loop.
For example on input
1
4
1 2 2 2
you print 2 while the answer is 1 (just delete the 1)
(Also, next time please just link your submission, don’t paste code in the comments)
1 Like
#include <bits/stdc++.h>
using namespace std;
int mostFrequent(int arr[], int n)
{
sort(arr, arr + n);
int max_count = 1, res = arr[0], curr_count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
curr_count++;
else {
if (curr_count > max_count) {
max_count = curr_count;
res = arr[i - 1];
}
curr_count = 1;
}
}
if (curr_count > max_count)
{
max_count = curr_count;
res = arr[n - 1];
}
return res;
}
// driver program
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,i;
cin>>t;
while(t--){
cin>>n;
int arr[n]; int count=0;
for(i=0;i<n;i++){
cin>>arr[i]; }
int x = mostFrequent(arr,n);
for(i=0;i<n;i++){
if((arr[i])!=x)
{ count++;} }
if(n==2)
{cout<<0<<endl;}
else if(n==3 and count>0)
{ cout<<1<<endl;}
else { cout<<count<<endl; } }
return 0; }
// For which testcase it is giving wrong answer ??
1
4
1 2 3 4
Answer is 2, you print 3.
1 Like
Thank you sir. I have improved my code and now got successful submission .
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
map<int,int> v;
for(int i=0;i<n;i++){
int x;
cin>>x;
v[x]++;
}
int m =-1;
if(n<3 && v.size()<3)
m=0;
else
if(n>=3 && v.size()>=3)
m=2;
else
for(auto it : v)
m = max(m,it.second);
if(m==0)
cout<<m<<endl;
else
cout<<n-m<<endl;
}
return 0;
}
pls tell me what is wrong in my code ,i pass every testcase of iceknight1093
1
5
3 1 2 2 2
sir thank for helping… I passed your testcase but my answer is wrong .
can pls explain what am i doing wrong @iceknigh1093
my code
map<int,int> v;
for(int i=0;i<n;i++){
int x;
cin>>x;
v[x]++;
}
int m =-1;
if(n<3 && v.size()<3)
m=0;
else
if(n==3 && v.size()==3)
m=1;
else
if(n>3 && v.size()>3
m=2;
else
for(auto it : v)
m = max(m,it.second);
if(m==0 || m ==1)
cout<<m<<endl;
else
cout<<n-m<<endl;
}
return 0;
}
1
6
1 2 3 4 4 4
You have too much pointless casework. Please go through the editorial and the code linked in it and use that to debug.
Also, please stop pasting your entire code in the comments. Just link your submission.