Skip to content

Practice X of a Kind in a Deck of Cards

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Easy#914
LeetCode Problem

X of a Kind in a Deck of Cards

Problem Statement

Return whether every card in deck can be partitioned into groups with one common size x greater than 1. All cards within a group must have the same value. Different groups may have different values, but their sizes must be equal.

Source: X of a Kind in a Deck of Cards on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
deck = [1,2,3,4,4,3,2,1]
Output
true
Explanation

Each of the values 1, 2, 3, and 4 appears twice. Choose the common group size x = 2 and form [1,1], [2,2], [3,3], and [4,4]. Every card is used and each group contains just one value, so the result is true. The shared group size must divide every value frequency; here their greatest common divisor is 2. The cards do not have to be adjacent in the original deck to be grouped together.

# Example 2

Input
deck = [1,1,1,2,2,2,3,3]
Output
false
Explanation

The frequencies of 1, 2, and 3 are 3, 3, and 2. A group size of 3 leaves the two 3-valued cards unusable, while a group size of 2 leaves one card over from each frequency of 3. Their greatest common divisor is 1, so no common size greater than 1 divides all three counts. Return false. It is not enough that every value appears at least twice; all groups must use the same size.

Constraints

1 <= deck.length <= 10^4
0 <= deck[i] < 10^4

How to solve X of a Kind in a Deck of Cards

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

The group size x must divide the count of every distinct value, so the question reduces to whether the greatest common divisor of all the frequencies is at least 2; the gcd is the largest size that divides everything, and some x greater than 1 works exactly when that gcd is greater than 1.

Why brute force is not enough

Count frequencies, then for each candidate x from 2 up to the smallest count test whether x divides every frequency. That is O(min count times distinct values) checks, which with deck.length up to 10^4 can reach tens of millions; the gcd approach replaces the loop with one fold over the counts.

Approach

  1. Build a frequency table from the deck using a hash map or an array sized to the value range, since values are below 10^4.
  2. Fold the greatest common divisor over all frequencies with the Euclidean algorithm, starting from the first count.
  3. The invariant is that after processing some counts, the running gcd is the largest size that divides each of them, so any x greater than 1 that works for all counts seen so far must divide it.
  4. Return true if the final gcd is at least 2, otherwise false.

Walkthrough of Example 2

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

  1. The frequencies are 3 for value 1, 3 for value 2, and 2 for value 3.
  2. The gcd of 3 and 3 is 3.
  3. The gcd of 3 and 2 is 1, since 3 mod 2 is 1 and 2 mod 1 is 0.
  4. The final gcd is 1, which is less than 2, so no common group size exists and the answer is false, as expected.

Time and space

Time O(n + d log C) · Space O(d). n is the deck size, d the number of distinct values, and C the largest count; each Euclidean step on two numbers up to C takes O(log C) and the table holds d entries.

Interview pitfalls

  • A deck with a single card, or any value appearing exactly once, forces the gcd to 1 and the answer false; candidates sometimes return true for a one-card deck.
  • Checking only that every frequency is at least 2, or that all frequencies are equal; frequencies 4 and 6 pass with x = 2 while 3 and 2 fail.
  • Using the minimum frequency as the group size instead of the gcd; frequencies 4 and 6 have minimum 4 but the only valid x is 2.
  • Testing divisibility by the total deck size or by the number of distinct values, which are unrelated to the group size.

Follow-up questions interviewers ask

  • What is the largest valid x, and how would you list all valid group sizes?
  • If groups were allowed to have different sizes but each at least 2, what single condition on the frequencies decides the answer?

Further reading on the technique: Euclidean algorithm

Related LeetCode Problems

Practice more problems similar to X of a Kind in a Deck of Cards.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.