LeetCode 914: X of a Kind in a Deck of Cards

Problem Restatement

We are given an integer array deck.

Each value represents the number written on one card.

We need to decide whether we can split the entire deck into groups such that:

Return True if such a partition is possible. Otherwise, return False. The official problem states the same grouping rule with x >= 2.

Input and Output

Function shape:

def hasGroupsSizeX(deck: list[int]) -> bool:
    ...

Examples

Example 1:

deck = [1, 2, 3, 4, 4, 3, 2, 1]

Counts:

1 -> 2
2 -> 2
3 -> 2
4 -> 2

We can choose:

x = 2

Groups:

[1, 1], [2, 2], [3, 3], [4, 4]

Answer:

True

Example 2:

deck = [1, 1, 1, 2, 2, 2, 3, 3]

Counts:

1 -> 3
2 -> 3
3 -> 2

There is no group size greater than 1 that divides all counts.

Answer:

False

Example 3:

deck = [1]

There is only one card.

Since x must be at least 2, no valid grouping exists.

Answer:

False

First Thought: Try Every Group Size

A direct method is to try every possible value of x.

The group size must be at least 2 and at most the smallest frequency.

For each x, check whether every card count is divisible by x.

from collections import Counter

class Solution:
    def hasGroupsSizeX(self, deck: list[int]) -> bool:
        counts = Counter(deck)

        smallest = min(counts.values())

        for x in range(2, smallest + 1):
            valid = True

            for count in counts.values():
                if count % x != 0:
                    valid = False
                    break

            if valid:
                return True

        return False

This works, but we can make the idea cleaner.

Key Insight

For a valid group size x, every card value count must be divisible by x.

So x must be a common divisor of all frequencies.

For example:

counts = [6, 9, 12]

A valid x must divide 6, 9, and 12.

Their greatest common divisor is:

gcd(6, 9, 12) = 3

Since this gcd is at least 2, we can choose x = 3.

So the problem becomes:

Find the greatest common divisor of all card frequencies. Return whether it is at least 2.

This is the standard solution.

Algorithm

1. Count how many times each card value appears.
2. Compute the gcd of all counts.
3. If the gcd is at least 2, return True.
4. Otherwise, return False.

Correctness

Let the frequency of each distinct card value be:

c1, c2, c3, ..., cm

If a valid group size x exists, then each frequency must be divisible by x.

That means x is a common divisor of all frequencies.

Since x >= 2, the greatest common divisor of all frequencies must also be at least 2.

So if a valid partition exists, the algorithm returns True.

Conversely, suppose the gcd of all frequencies is g, where g >= 2.

Then every frequency is divisible by g.

For each card value, we can split its cards into groups of size g.

Each group contains only one card value, and every group has the same size g.

So a valid partition exists.

Therefore, the algorithm returns True exactly when the deck can be partitioned as required.

Complexity

More precisely, gcd is computed over the number of distinct values, but O(n log n) is a safe bound.

Implementation

from collections import Counter
from math import gcd

class Solution:
    def hasGroupsSizeX(self, deck: list[int]) -> bool:
        counts = Counter(deck)

        group_gcd = 0

        for count in counts.values():
            group_gcd = gcd(group_gcd, count)

        return group_gcd >= 2

Code Explanation

Count card frequencies:

counts = Counter(deck)

For example:

deck = [1, 1, 2, 2, 2, 2]

gives:

1 -> 2
2 -> 4

Initialize gcd as 0:

group_gcd = 0

This works because:

gcd(0, x) = x

Then fold all counts into one gcd value:

for count in counts.values():
    group_gcd = gcd(group_gcd, count)

Finally, the deck can be grouped only if the common divisor is at least 2:

return group_gcd >= 2

Testing

def run_tests():
    s = Solution()

    assert s.hasGroupsSizeX([1, 2, 3, 4, 4, 3, 2, 1]) is True
    assert s.hasGroupsSizeX([1, 1, 1, 2, 2, 2, 3, 3]) is False
    assert s.hasGroupsSizeX([1]) is False
    assert s.hasGroupsSizeX([1, 1]) is True
    assert s.hasGroupsSizeX([1, 1, 2, 2, 2, 2]) is True
    assert s.hasGroupsSizeX([0, 0, 0, 0]) is True
    assert s.hasGroupsSizeX([1, 1, 1, 1, 2, 2]) is True

    print("all tests passed")

run_tests()

Test meaning: