title
In a deck of cards, each card has an integer written on it.
Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:
Each group has exactly X cards. All the cards in each group have the same integer.
Example 1:
Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]
Example 2:
Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.
Example 3:
Input: [1]
Output: false
Explanation: No possible partition.
Example 4:
Input: [1,1]
Output: true
Explanation: Possible partition [1,1]
Example 5:
Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]
solution
先计数，计数后求这些count的最小公倍数
class Solution {
public:
int gcd(int a, int b) {
return b == 0 ? a:gcd(b,a%b) ;
}
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> map1;
if (deck.size() < 2) return false;
int minx = INT_MAX;
for (auto &it : deck) {
map1[it]++;
}
for (auto &it : map1) {
if (minx == INT_MAX) {
minx = it.second;
}
else {
minx = gcd(minx, it.second);
}
}
return minx >= 2;
}
};