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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

X of a Kind in a Deck of Cards

Difficulty: Easy

Problem Description

You are given an integer array deck where deck[i] represents the number written on the i-th card. Partition the cards into one or more groups such that:

  • Each group has exactly x cards where x > 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.

Key Insights

  • Each unique card number must appear in the deck at least x times for some integer x > 1.
  • The greatest common divisor (GCD) of the counts of each unique card number must be greater than 1 for a valid partition.
  • If there's a single unique card, it cannot form a valid group of size greater than 1.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the deck (to count occurrences). Space Complexity: O(k), where k is the number of unique cards.

Solution

To solve the problem, we can use a frequency count to determine how many times each card appears in the deck. After counting the occurrences of each card, we can calculate the GCD of these counts. If the GCD is greater than 1, we can partition the cards into groups of size x where x is the GCD. Otherwise, it is not possible to create the required groups.

Steps:

  1. Count the frequency of each card using a hash table (or dictionary).
  2. Compute the GCD of all the frequencies.
  3. Check if the GCD is greater than 1.

Code Solutions

from collections import Counter
from math import gcd
from functools import reduce

def hasGroupsSizeX(deck):
    count = Counter(deck)
    freq = list(count.values())
    
    # Calculate the GCD of all frequencies
    gcd_value = reduce(gcd, freq)
    
    # Return True if GCD is greater than 1
    return gcd_value > 1
← Back to All Questions