914. X of a Kind in a Deck of Cards #

Problem #

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: 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.

Example 3:

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

Example 4:

Input: deck = [1,1]
Output: true
Explanation: Possible partition [1,1].

Example 5:

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

Problem Summary #

Given a deck of cards, each card has an integer written on it. At this point, you need to choose a number X so that we can split the entire deck into 1 or more groups according to the following rules:

Each group has X cards.
All cards in the group have the same integer written on them.

Return true if and only if the X you can choose is >= 2.

Solution Approach #

Given a deck of cards, we need to choose a number X so that each group has X cards and the numbers on the cards in each group are the same. When X ≥ 2, output true.
By analyzing the problem, we can know that only when X is a divisor of all counts, that is, a divisor of the greatest common divisor of all counts, can a valid grouping possibly exist. Therefore, we only need to find the greatest common divisor g of all counts and determine whether g is greater than or equal to 2. If it is greater than or equal to 2, the condition is satisfied; otherwise, it is not satisfied.
Time complexity: O(NlogC), where N is the number of cards, and C is the range of numbers in the array deck, which is 10000 in this problem. The complexity of finding the greatest common divisor of two numbers is O(logC), and it needs to be computed at most N - 1 times. Space complexity: O(N + C) or O(N).

Code #


package leetcode

func hasGroupsSizeX(deck []int) bool {
	if len(deck) < 2 {
		return false
	}
	m, g := map[int]int{}, -1
	for _, d := range deck {
		m[d]++
	}
	for _, v := range m {
		if g == -1 {
			g = v
		} else {
			g = gcd(g, v)
		}
	}
	return g >= 2
}

func gcd(a, b int) int {
	if a == 0 {
		return b
	}
	return gcd(b%a, a)
}