PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Utkarsh Gupta
Preparer: Jeevan Jyot Singh
Testers: Abhinav Sharma, Venkata Nikhil Medam
Editorialist: Nishank Suresh
DIFFICULTY:
1171
PREREQUISITES:
Frequency tables
PROBLEM:
Given an array A, report whether it has a dominant element, i.e, an element whose frequency is larger than the frequency of any other element.
EXPLANATION:
Let M be the maximum frequency of any element in A. Then,
- If there are two or more elements with frequency M, there cannot be a dominant element
- Otherwise, there is a unique element with frequency M, which is a dominant element
To check these cases, all that needs to be done is to know the frequency of every element of A. Note that computing frequencies by iterating across the entire array each time might be too slow, because it can be a complexity of \mathcal{O}(N^2) in the worst case.
Instead, we build the frequency array of A. This can be done as follows:
- Let F be our frequency array. Since every element in A lies between 1 and N, it is enough to have F be of length N.
- Initialize F with zeroes.
- Then, for each i from 1 to N, add 1 to F_{A_i}.
- At the end of this, F_x holds the number of times x appears in A.
Now that we have F, we can solve the problem as mentioned in the first step. Let M be the maximum element of F, and then check whether M appears exactly once in F (in which case the answer is “Yes”) or more than once (in which case the answer is “No”).
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
CODE:
Tester (C++)
// Tester: Nikhil_Medam
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 1e3 + 5;
int t, n, a[N];
unordered_map<int,int> freq;
int32_t main() {
cin >> t;
while(t--) {
freq.clear();
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
freq[a[i]]++;
}
int max_freq = 0, max_freq_count = 0;
for(auto &i: freq) {
if(i.second > max_freq) {
max_freq = i.second;
max_freq_count = 1;
}
else if(i.second == max_freq) {
max_freq_count++;
}
}
if(max_freq_count == 1) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}
Editorialist (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = [0]*(n+1)
for x in a:
freq[x] += 1
mx = max(freq)
print('yes' if freq.count(mx) == 1 else 'no')