We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

X of a Kind in a Deck of Cards

Number: 950

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an integer array deck, where deck[i] represents the number written on the ith card, determine if it is possible to partition the deck into one or more groups such that each group has exactly x cards (with x > 1) and every card in the group has the same integer.

Key Insights

  • Count the frequency of each card using a hash table.
  • The deck can be partitioned accordingly if and only if there exists a common divisor greater than 1 for all frequency counts.
  • Using the Greatest Common Divisor (GCD) is an efficient way to check for this common divisor.

Space and Time Complexity

Time Complexity: O(n + m * log(max count)), where n is the number of cards and m is the number of unique cards.
Space Complexity: O(m), where m is the number of unique cards stored in the frequency counter.

Solution

The solution uses a hash map (or dictionary) to count the number of occurrences for each card in the deck. With these frequencies, compute the GCD of all the counts. If the obtained GCD is at least 2, then the deck can be partitioned into groups of that size, ensuring each group has cards with the same integer. This approach leverages number theory to efficiently determine the possibility of partitioning.

Code Solutions

def hasGroupsSizeX(deck):
    from collections import Counter
    from math import gcd
    # Step 1: Count the occurrences of each card.
    count = Counter(deck)
    # Step 2: Compute the gcd of all frequency counts.
    group_gcd = 0
    for freq in count.values():
        group_gcd = gcd(group_gcd, freq)
    # Step 3: Return True if the gcd is at least 2, otherwise False.
    return group_gcd >= 2

# Example usage:
print(hasGroupsSizeX([1,2,3,4,4,3,2,1]))
← Back to All Questions