Difficulty: Easy | Acceptance: 30.30% | Paid: No Topics: Array, Hash Table, Math, Counting, Number Theory
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.
Examples
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 <= 10⁴
0 <= deck[i] < 10⁴
- Examples
- Constraints
- Approach 1: Counting and GCD
- Approach 2: Brute Force Group Size
Examples
Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].
Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.
Input: deck = [1]
Output: false
Explanation: No possible partition.
Constraints
1 <= deck.length <= 10⁴
0 <= deck[i] < 10⁴
Approach 1: Counting and GCD
Intuition If we count the frequency of each card, the group size X must divide the count of every card type. The largest possible X is the Greatest Common Divisor (GCD) of all frequencies. If the GCD is at least 2, a valid partition exists.
Steps
- Count the frequency of each number in the deck using a hash map.
- Compute the GCD of all the frequency values.
- Return true if the GCD is greater than or equal to 2, otherwise return false.
from collections import Counter
from math import gcd
from functools import reduce
from typing import List
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
counts = Counter(deck).values()
return reduce(gcd, counts) >= 2
Complexity
- Time: O(N * log(M)), where N is the size of the deck and M is the maximum frequency.
- Space: O(N) to store the frequency counts.
- Notes: This is the most efficient approach, leveraging number theory to avoid unnecessary iterations.
Approach 2: Brute Force Group Size
Intuition Since the group size X must be at least 2 and cannot exceed the minimum frequency of any card, we can iterate through all possible values of X from 2 up to the minimum frequency. For each X, we check if it divides all card frequencies.
Steps
- Count the frequency of each number.
- Find the minimum frequency among all cards.
- Iterate X from 2 to the minimum frequency (inclusive).
- For each X, check if every frequency is divisible by X.
- If such an X is found, return true. If the loop finishes without success, return false.
from collections import Counter
from typing import List
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
if len(deck) < 2:
return False
counts = Counter(deck)
min_count = min(counts.values())
if min_count < 2:
return False
for x in range(2, min_count + 1):
if all(c % x == 0 for c in counts.values()):
return True
return False
Complexity
- Time: O(N * M), where N is the size of the deck and M is the minimum frequency.
- Space: O(N) to store the frequency counts.
- Notes: This approach is straightforward but can be slower than the GCD method if the minimum frequency is large.