X of a Kind in a Deck of Cards

X of a Kind in a Deck of Cards

What is this problem about?

You are given an array of integers representing cards in a deck. You need to determine if you can partition the entire deck into one or more groups such that:

1. Each group has the same number of cards X.
2. All cards in each group are of the same value.
3. X >= 2.

Why is this asked in interviews?

This is a great "Easy" problem that transitions from Counting to Number Theory. Companies like Amazon ask this to see if you can identify that the common group size X must be a divisor of the frequency of every card value in the deck. This leads directly to the concept of the Greatest Common Divisor (GCD).

Algorithmic pattern used

The pattern is Frequency Counting and GCD.

1. Count the frequency of each card using a hash map or an array.
2. Find the GCD of all these frequencies.
3. If the final GCD is greater than or equal to 2, return true.

Example explanation

Deck: [1, 2, 3, 4, 4, 3, 2, 1].

1. Frequencies: 1: 2, 2: 2, 3: 2, 4: 2.
2. GCD(2, 2, 2, 2) = 2.
3. Since 2 >= 2, we can partition them into groups of 2. True. Deck: [1, 1, 1, 2, 2, 2, 2, 2, 2].
4. Frequencies: 1: 3, 2: 6.
5. GCD(3, 6) = 3.
6. Since 3 >= 2, we can partition them into groups of 3. True.

Common mistakes candidates make

• Only checking parity: Thinking that if all counts are even, it's true, but forgetting about odd numbers like 3 or 5 (e.g., all counts could be 3).
• Not using GCD: Trying to find the minimum frequency and checking if it divides others (this fails if the minimum is 4 but others are 6—GCD is 2).
• Ignoring the X >= 2 condition: Returning true when the GCD is 1.

Interview preparation tip

Remember the Euclidean Algorithm for finding the GCD: gcd(a, b) = gcd(b, a % b). It is a tiny bit of code that is incredibly useful in competitive programming and technical interviews.