X of a Kind in a Deck of Cards: GCD to the Rescue

LeetCode 914. X of a Kind in a Deck of Cards gives you a deck of cards where each card has an integer written on it. You need to decide whether you can split the deck into one or more groups such that each group has exactly X cards (with X >= 2) and every card in a group shows the same number.

It looks like a grouping problem, but the real trick is a number theory idea: the greatest common divisor.

The problem

Given an array deck of integers, return True if you can choose some integer X >= 2 such that the deck can be partitioned into groups of size X, where every card in each group has the same value.

For example, deck = [1, 2, 3, 4, 4, 3, 2, 1] can be split into four groups of 2: {1,1}, {2,2}, {3,3}, {4,4}. So the answer is True.

The brute force approach

One way to solve this is to try every possible group size X from 2 up to the length of the deck. For each candidate X, check whether every card value's frequency is divisible by X. If you find any X that works, return True.

from collections import Counter

def has_groups_size_x(deck: list[int]) -> bool:
    counts = Counter(deck)
    for x in range(2, len(deck) + 1):
        if all(c % x == 0 for c in counts.values()):
            return True
    return False

This works, but it is wasteful. You are testing every possible X individually when there is a single number that tells you exactly which values of X work: the GCD of all frequencies.

The key insight

If you count how many times each card value appears, the question becomes: is there some X >= 2 that divides every frequency? That is exactly what the GCD answers. The GCD of a set of numbers is the largest number that divides all of them, and every divisor of the GCD also divides all of them.

So the algorithm reduces to:

1. Count the frequency of each card value.
2. Compute the GCD of all the frequencies.
3. If the GCD is at least 2, return True. Otherwise, return False.

Step-by-step walkthrough

The code

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

def has_groups_size_x(deck: list[int]) -> bool:
    counts = Counter(deck)
    g = reduce(gcd, counts.values())
    return g >= 2

The function counts each card value's frequency with Counter, then folds gcd across all frequency values using reduce. If the resulting GCD is 2 or greater, the deck can be partitioned.

Complexity analysis

Here n is the number of cards, k is the number of distinct values, and m is the maximum frequency. Building the counter is O(n). Computing the GCD across k values costs O(k log m) since each gcd call is O(log m). In practice this runs in near-linear time.

The building blocks

This problem combines two reusable pieces that come up across many other problems.

1. Frequency counting with a hash map

Build a map from values to their counts. This is the same pattern you use in Group Anagrams, Top K Frequent Elements, and Valid Anagram. The idea is always the same: one pass to count, then process the counts.

from collections import Counter
counts = Counter(collection)

2. GCD reduction

Fold a two-argument GCD function across a collection of numbers to find the GCD of the entire set. This is a handy technique whenever a problem asks whether some number divides all members of a group, or asks for the largest such divisor. You will see it in problems involving LCM, modular arithmetic, and fraction simplification.

from math import gcd
from functools import reduce
g = reduce(gcd, values)

Edge cases

• All cards are the same: Every frequency is n, and gcd(n) = n. As long as there are at least 2 cards, the answer is True.
• Every card is unique: Every frequency is 1, and gcd(1, 1, ...) = 1. Since 1 < 2, the answer is False.
• Mixed frequencies like [1,1,2,2,2,2]: Frequencies are {1:2, 2:4}. gcd(2, 4) = 2, which is >= 2. You can split into groups of 2: {1,1}, {2,2}, {2,2}.
• Single card: Only one card means you cannot form a group of size >= 2. The frequency is 1, GCD is 1, so the answer is False.
• Deck with one value repeated many times: [7,7,7,7,7,7] has frequency 6. gcd(6) = 6, which is >= 2. Valid groupings include X=2, X=3, or X=6.

From understanding to recall

The GCD insight is the kind of thing that feels obvious once you see it but is easy to miss under pressure. Most people start by thinking about trying every possible group size, and only later realize that the GCD encodes exactly the information they need. Bridging that gap is about pattern recognition, not raw intelligence.

Spaced repetition helps you internalize both building blocks independently. When you drill frequency counting on its own, it becomes automatic. When you drill GCD reduction on its own, you build intuition for when divisibility questions arise. The next time you see a problem that combines them, you will recognize both pieces and snap them together.

That is the difference between understanding a solution and being able to produce one. Reading this walkthrough gives you the first. Deliberate practice gives you the second.

Related posts

• Group Anagrams - Another problem where frequency counting is the first step, then you group by a derived key
• Happy Number - A math-based problem that also requires recognizing a non-obvious structural property
• Contains Duplicate - The simplest hash set problem, using the same counting foundation