X loại trong bộ bài trong C++

Mô tả bài toán

Cho bộ bài (mảng số nguyên). Kiểm tra có tồn tại X ≥ 2 sao cho có thể chia toàn bộ bộ bài thành các nhóm, mỗi nhóm đúng X lá và tất cả lá trong nhóm có cùng số.

Ví dụ: deck = [1,2,3,4,4,3,2,1] → True (chia thành [1,1],[2,2],[3,3],[4,4], X=2).

Giải pháp (Ước chung lớn nhất - GCD)

• Đếm tần suất mỗi số trong deck.
• Tính GCD của tất cả các tần suất.
• Nếu GCD ≥ 2 → trả về true, ngược lại false.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> mp;
        int ans = 0;
        for (int x : deck) mp[x]++;
        for (auto& [_, cnt] : mp) ans = __gcd(ans, cnt);
        return ans > 1;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,4,3,2,1};
    cout << ob.hasGroupsSizeX(v);
    return 0;
}

Đầu vào

{1,2,3,4,4,3,2,1}

Đầu ra

1