高橋くんが転入する前における、クラスの人数の最大値を \(M\) とします。

クラスの人数の最大値が高橋くんの転入で減ることはないので、高橋くんが転入したクラスの人数は高橋くんを含めて \(M\) 人以上でなければなりません。 逆に、この条件を満たせば高橋くんは喜びます。

よって、求めるものは高橋くんが転入する前に \(M-1\) 人以上いるクラスがいくつあるかです。 すべてのクラスについて高橋くんが転入する前の人数を求め、これが \(M-1\) 人以上となるクラスの個数を数えればよいです。

時間計算量は \(O(N)\) となります。

実装例は以下のようになります。

#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); // 最大値を M として
    int ans = 0;
    for (int i = 0; i < K; ++i) {
        if (member_count[i] >= M - 1) { // M - 1 人以上のクラスの個数を数える
            ++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) # 最大値を M として
ans = 0
for c in member_count:
    if c >= M - 1: # M - 1 人以上のクラスの個数を数える
        ans += 1

print(ans)