# 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:

| Rule | Meaning |
|---|---|
| Same group size | Every group has exactly `x` cards |
| Minimum group size | `x > 1` |
| Same card value | All cards in one group have the same integer |

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

| Item | Meaning |
|---|---|
| Input | Integer array `deck` |
| Output | Boolean |
| Group size | Same `x` for every group |
| Constraint | `x >= 2` |
| Group content | All cards in a group must have the same value |

Function shape:

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

## Examples

Example 1:

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

Counts:

```python
1 -> 2
2 -> 2
3 -> 2
4 -> 2
```

We can choose:

```python
x = 2
```

Groups:

```python
[1, 1], [2, 2], [3, 3], [4, 4]
```

Answer:

```python
True
```

Example 2:

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

Counts:

```python
1 -> 3
2 -> 3
3 -> 2
```

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

Answer:

```python
False
```

Example 3:

```python
deck = [1]
```

There is only one card.

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

Answer:

```python
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`.

```python
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:

```python
counts = [6, 9, 12]
```

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

Their greatest common divisor is:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | We count cards and compute gcd values |
| Space | `O(n)` | The frequency map may store many distinct card values |

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

## Implementation

```python
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:

```python
counts = Counter(deck)
```

For example:

```python
deck = [1, 1, 2, 2, 2, 2]
```

gives:

```python
1 -> 2
2 -> 4
```

Initialize gcd as `0`:

```python
group_gcd = 0
```

This works because:

```python
gcd(0, x) = x
```

Then fold all counts into one gcd value:

```python
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`:

```python
return group_gcd >= 2
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 4, 3, 2, 1]` | All counts are `2` |
| `[1, 1, 1, 2, 2, 2, 3, 3]` | Counts have gcd `1` |
| `[1]` | Cannot form group size at least `2` |
| `[1, 1]` | One valid group |
| `[1, 1, 2, 2, 2, 2]` | Counts `2` and `4` share divisor `2` |
| `[0, 0, 0, 0]` | Card value can be `0` |
| `[1, 1, 1, 1, 2, 2]` | Counts `4` and `2` share divisor `2` |