Let \(M\) be the maximum number of students in a class before Takahashi transfers.

The number of students does not reduce by his transfer, so it is necessary that the class he belongs to has at least \(M\) student including himself. Conversely, he will be happy if this is satisfied.

Hence, the desired value is the number of classes with \(M-1\) or more students before his transfer. Find the number of students for all classes before his transfer, and count the number of classes where the student count is \(M-1\) or greater.

The time complexity is \(O(N)\).

The following is sample code.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> member_count(K);
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        ++member_count[--A];
    }

    int M = ranges::max(member_count); // Let M be the maximum value
    int ans = 0;
    for (int i = 0; i < K; ++i) {
        if (member_count[i] >= M - 1) { // Count the number of classes with (M - 1) or more students
            ++ans;
        }
    }

    cout << ans << endl;
    return 0;
}

N, K = map(int, input().split())

member_count = [0 for i in range(K)]
for A in map(int, input().split()):
    member_count[A - 1] += 1

M = max(member_count) # Let M be the maximum value
ans = 0
for c in member_count:
    if c >= M - 1: # Count the number of classes with (M - 1) or moe students
        ans += 1

print(ans)