LeetCode 0914. X of a Kind in a Deck of Cards Solution in Java, C++, Python & More | Explanation + Code

Description

You are given an integer array deck where deck[i] represents the number written on the ith card.

Partition the cards into one or more groups such that:

• Each group has exactly x cards where x > 1, and
• All the cards in one group have the same integer written on them.

Return true if such partition is possible, or false otherwise.

 

Example 1:

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:

Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

 

Constraints:

• 1 <= deck.length <= 104
• 0 <= deck[i] < 104

Solutions

Solution 1: Greatest Common Divisor

First, we use an array or hash table cnt to count the occurrence of each number. Only when X is a divisor of the greatest common divisor of all cnt[i], can it satisfy the problem's requirement.

Therefore, we find the greatest common divisor g of the occurrence of all numbers, and then check whether it is greater than or equal to 2.

The time complexity is O(n × log M), and the space complexity is O(n + log M). Where n and M are the length of the array deck and the maximum value in the array deck, respectively.

PythonJavaC++GoTypeScript

class Solution: def hasGroupsSizeX(self, deck: List[int]) -> bool: cnt = Counter(deck) return reduce(gcd, cnt.values()) >= 2(code-box)

class Solution { public boolean hasGroupsSizeX(int[] deck) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : deck) { cnt.merge(x, 1, Integer::sum); } int g = cnt.get(deck[0]); for (int x : cnt.values()) { g = gcd(g, x); } return g >= 2; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }(code-box)

class Solution { public: bool hasGroupsSizeX(vector<int>& deck) { unordered_map<int, int> cnt; for (int x : deck) { ++cnt[x]; } int g = cnt[deck[0]]; for (auto& [_, x] : cnt) { g = gcd(g, x); } return g >= 2; } };(code-box)

func hasGroupsSizeX(deck []int) bool { cnt := map[int]int{} for _, x := range deck { cnt[x]++ } g := cnt[deck[0]] for _, x := range cnt { g = gcd(g, x) } return g >= 2 } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }(code-box)

function hasGroupsSizeX(deck: number[]): boolean { const cnt: Record<number, number> = {}; for (const x of deck) { cnt[x] = (cnt[x] || 0) + 1; } const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b)); let g = cnt[deck[0]]; for (const [_, x] of Object.entries(cnt)) { g = gcd(g, x); } return g >= 2; }(code-box)