## Description

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. 1 <= deck.length <= 10000
2. 0 <= deck[i] < 10000

## Solutions

### 1. Hash Table

本来想着直接存一个字典，看下 value 值是否都一样就可以了，后来发现，这个 group 里的值也可以和其他的 group 里的值一样，于是参考得到一个解决办法是，只要所有 value 值的最大公约数是大于 1 的，就说明多的那些可以拆成大小一致的 group！

from functools import reduce
# Time: O(n)
# Space: O(n)
class Solution:
def hasGroupsSizeX1(self, deck: List[int]) -> bool:
def gcd(a, b):
while b:
a, b = b, a % b
return a
count = collections.Counter(deck).values()
return reduce(gcd, count) > 1

def hasGroupsSizeX(self, deck: List[int]) -> bool:
count = collections.Counter(deck).values()
res = 0
for cnt in count:
res = self.gcd(cnt, res)
return res > 1

def gcd(self, a, b):
while b:
a, b = b, a % b
return a

# 74/74 cases passed (144 ms)
# Your runtime beats 56.29 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


### 2. Array

先给 nums 排序，接着两层遍历：

• 让 i 从 2 开始往后面遍历，把 i 当做每个 group 的大小
• 在每一次遍历中，再从 0 开始检查没 i 个连续子数组转成 set 后大小是否为 1，是就返回真
# Time: O(n^2)
# Space: O(n)
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
n = len(deck)
deck.sort()
for i in range(2, n+1):
if n % i == 0:
flag = True
j = 0
while j < n:
if len(set(deck[j:j+i])) != 1:
flag = False
j += i
if flag:
return True
return False
# 69/69 cases passed (164 ms)
# Your runtime beats 14.11 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)