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).
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.
#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)
#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.
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.
1
5
1 2 3 3 3
but what if the array was 1,2,3,4,5 so here max_freq = 1 so min(5-1, 5-2) = min(4,3) = 3
so, elements would be 1,2,3 but [1,2 & 2,1] = 1; [1,3 & 3,1] = 2 & [2,3 & 3,2] = 1 here not all are equal???