Welcome to Subscribe On Youtube
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.
-
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; } } ############ class Solution { public boolean hasGroupsSizeX(int[] deck) { int[] cnt = new int[10000]; for (int v : deck) { ++cnt[v]; } int g = -1; for (int v : cnt) { if (v > 0) { g = g == -1 ? v : gcd(g, v); } } return g >= 2; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
-
// 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: def hasGroupsSizeX(self, deck: List[int]) -> bool: vals = Counter(deck).values() return reduce(gcd, vals) >= 2 ############ 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
-
func hasGroupsSizeX(deck []int) bool { cnt := make([]int, 10000) for _, v := range deck { cnt[v]++ } g := -1 for _, v := range cnt { if v > 0 { if g == -1 { g = v } else { g = gcd(g, v) } } } return g >= 2 } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }