914. X of a Kind in a Deck of Cards
Model: qwen2.5-coder:14b
Topics: Array,Math
FAANG asked: 1
Acceptance rate: 34.0%
Problem Breakdown
The problem asks us to determine if we can split a deck of cards into groups where each group has exactly X cards, with all cards in each group having the same integer. The input is an array of integers representing the cards in the deck. The output should be a boolean indicating whether such a partition is possible.
Inputs:
- An array of integers
deck, where each integer represents a card.
Outputs:
- A boolean value (
trueorfalse) indicating if it’s possible to split the deck as described.
Implicit Constraints/Edge Cases:
- The length of the deck can range from 1 to 10,000.
- Each card has an integer value between 0 and 9,999.
- If the deck has fewer than 2 cards, it’s impossible to split into groups of size
X >= 2, so the output should befalse. - The deck might contain duplicate cards or all unique cards.
Intuition
A brute-force approach would involve trying every possible value of X from 2 up to half the length of the deck and checking if we can partition the deck into groups of size X. However, this approach is inefficient due to its high time complexity.
The key insight is that for a valid partition to exist, the number of cards of each unique integer must be divisible by some common factor X >= 2. Therefore, we need to find the greatest common divisor (GCD) of these frequencies. If this GCD is at least 2, then it’s possible to split the deck as required.
Approach
- Count Frequencies: Use a dictionary or an array to count the frequency of each integer in the deck.
- Compute GCD: Calculate the GCD of these frequencies.
- Check Divisibility: If the GCD is at least 2, return
true; otherwise, returnfalse.
Data Structures:
- A dictionary to store the frequency of each card integer.
Complexity Analysis
- Time Complexity: O(n log k), where n is the number of cards in the deck and k is the maximum count of any single card integer. The GCD computation takes O(log k) time.
- Space Complexity: O(m), where m is the number of unique integers in the deck.
Solution
from collections import Counter
import math
def hasGroupsSizeX(deck):
# Step 1: Count the frequency of each card integer
freq = Counter(deck)
# Step 2: Compute the GCD of all frequencies
gcd_value = freq[deck[0]]
for count in freq.values():
gcd_value = math.gcd(gcd_value, count)
# Step 3: Check if the GCD is at least 2
return gcd_value >= 2
# Example usage:
print(hasGroupsSizeX([1,2,3,4,4,3,2,1])) # Output: True
print(hasGroupsSizeX([1,1,1,2,2,2,3,3])) # Output: False
print(hasGroupsSizeX([1])) # Output: False
print(hasGroupsSizeX([1,1])) # Output: True
print(hasGroupsSizeX([1,1,2,2,2,2])) # Output: True
Edge Cases Handled
- Single Card: If the deck has only one card, it’s impossible to split into groups of size
X >= 2, so the function returnsfalse. - All Unique Cards: The GCD calculation will handle cases where all cards are unique.
- All Identical Cards: The GCD will be equal to the count of the single integer, and if this count is at least 2, the function returns
true.