914. X of a Kind in a Deck of Cards
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 wherex > 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 \times \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.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|