X Of A Kind In A Deck Of Cards Problem
Description
LeetCode Problem 914.
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:
1
2
3
Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].
Example 2:
1
2
3
Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.
Example 3:
1
2
3
Input: deck = [1]
Output: false
Explanation: No possible partition.
Example 4:
1
2
3
Input: deck = [1,1]
Output: true
Explanation: Possible partition [1,1].
Example 5:
1
2
3
Input: deck = [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2].
Constraints:
- 1 <= deck.length <= 10^4
- 0 <= deck[i] < 10^4
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> m;
for (int i = 0; i < deck.size(); i ++) {
if (m.find(deck[i]) == m.end())
m[deck[i]] = 0;
m[deck[i]] ++;
}
int g = -1;
for (auto x : m) {
if (g == -1)
g = x.second;
else {
g = gcd(g, x.second);
if (g < 2)
return false;
}
}
return (g >= 2);
}
};