Why is this this solution not accepted?
I count the frequency of each element using a map, keeping track of which is the most frequent.
If there are any zeros in the bucket, I add them all to the most frequent element.
Then, I iterate over the bucket to calculate the answer using the formula (freq[i]) * (freq[i] - 1) / 2, where freq[i] is the frequency of the ith number in my bucket.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, int> bucket;
int maxi = 0;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
if (++bucket[num] > bucket[maxi]) {
maxi = num;
};
};
int answer = 0, zeros = bucket[0];
if (zeroes) {
bucket[0] -= zeroes;
bucket[maxi] += zeroes;
};
for (const pair<int, int> &entry : bucket) {
int count = entry.second;
answer += (count) * (count - 1) / 2;
};
cout << answer << '\n';
};
return 0;
};
I also tried counting the zeros separately as the editorial suggests, but this doesn’t work either.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, int> bucket;
int maxi = 0;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
maxi = max(maxi, ++bucket[num]);
};
int answer = 0, zeros = bucket[0];
if (zeros && bucket.size() > 1) {
bucket.erase(begin(bucket));
answer += zeros * maxi;
answer += zeros * (zeros - 1) / 2;
};
for (const pair<int, int> &entry : bucket) {
int count = entry.second;
if (count > 1) {
answer += (count) * (count - 1) / 2;
};
};
cout << answer << '\n';
};
return 0;
};
Any suggestion would be appreciated.