Formatted question description: https://leetcode.ca/all/914.html
914. X of a Kind in a Deck of Cards (Easy)
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]
Note:
1 <= deck.length <= 10000
0 <= deck[i] < 10000
Companies:
Google
Solution 1.
// OJ: https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// Time: O(N^2loglogN)
// Space: O(N)
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> cnt;
for (int n : deck) cnt[n]++;
int minCnt = INT_MAX;
for (auto p : cnt) minCnt = min(minCnt, p.second);
if (minCnt == 1) return false;
for (int x = 2; x <= minCnt; ++x) {
bool found = true;
for (auto p : cnt) {
if (p.second % x) {
found = false;
break;
}
}
if (found) return true;
}
return false;
}
};
Java
-
class Solution { public boolean hasGroupsSizeX(int[] deck) { Map<Integer, Integer> countMap = new HashMap<Integer, Integer>(); for (int num : deck) { int count = countMap.getOrDefault(num, 0); count++; countMap.put(num, count); } int gcd = 0; Set<Integer> keySet = countMap.keySet(); for (int num : keySet) { int count = countMap.get(num); gcd = gcd(gcd, count); } return gcd >= 2; } public int gcd(int num1, int num2) { if (num1 == 0 && num2 == 0) return 1; while (num1 != 0 && num2 != 0) { if (num1 > num2) { int temp = num1; num1 = num2; num2 = temp; } num2 %= num1; } return num1 == 0 ? num2 : num1; } }
-
// OJ: https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/ // Time: O(N^2loglogN) // Space: O(N) class Solution { public: bool hasGroupsSizeX(vector<int>& deck) { unordered_map<int, int> cnt; for (int n : deck) cnt[n]++; int minCnt = INT_MAX; for (auto p : cnt) minCnt = min(minCnt, p.second); if (minCnt == 1) return false; for (int x = 2; x <= minCnt; ++x) { bool found = true; for (auto p : cnt) { if (p.second % x) { found = false; break; } } if (found) return true; } return false; } };
-
class Solution(object): def hasGroupsSizeX(self, deck): """ :type deck: List[int] :rtype: bool """ count = collections.Counter(deck) X = min(count.values()) for x in range(2, X + 1): if all(v % x == 0 for v in count.values()): return True return False