# X of a Kind in a Deck of Cards
**Difficulty:** EASY
[External](https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards)
Canonical: https://scaleengineer.com/dsa/problems/x-of-a-kind-in-a-deck-of-cards
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `deck` where `deck[i]` represents the number written on the `ith` card.

Partition the cards into **one or more groups** such that:

* Each group has **exactly** `x` cards where `x > 1`, and
* All the cards in one group have the same integer written on them.

Return `true` _if such partition is possible, or_ `false` _otherwise_.

**Example 1:**

**Input:** deck = [1,2,3,4,4,3,2,1]
**Output:** true
**Explanation**: Possible partition [1,1],[2,2],[3,3],[4,4].

**Example 2:**

**Input:** deck = [1,1,1,2,2,2,3,3]
**Output:** false
**Explanation**: No possible partition.

**Constraints:**

* `1 <= deck.length <= 104`
* `0 <= deck[i] < 104`

# Approaches
## Brute Force by Trial Division
This approach first counts the occurrences of each card number. Then, it iterates through all possible group sizes `x` (from 2 up to the minimum count of any card) and checks if `x` can divide all the card counts evenly. If such an `x` is found, it means a valid partition is possible.
**Time:** O(N + U * C_min), where N is the number of cards, U is the number of unique cards, and C_min is the minimum frequency. Counting frequencies takes O(N). The outer loop runs C_min times, and the inner loop runs U times. In the worst case, this can be close to O(N^2). · **Space:** O(U), where U is the number of unique cards. This is for storing the frequency map. In the worst case, U can be equal to N (the total number of cards), making the space complexity O(N).
**Pros:** Conceptually simple and easy to understand.; Straightforward to implement without requiring advanced mathematical concepts.
**Cons:** Inefficient for large inputs, especially when the minimum frequency is large.; The time complexity can be high, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The most straightforward way to solve this problem is to simulate the check for every possible group size `x`. 

First, we need to know the counts of each type of card. A hash map is a suitable data structure for this, mapping each card number to its frequency in the deck.

Once we have the counts, we know that any valid group size `x` must divide every single one of these counts. The smallest possible group size is 2, and the largest possible group size cannot exceed the count of the least frequent card. Let's call this minimum frequency `min_freq`.

So, we can simply test every integer `x` from 2 to `min_freq`. For each `x`, we iterate through all the frequencies we counted and check if `count % x == 0`. If this condition holds true for all counts, we have found a valid `x` and can immediately return `true`. If we check all possible values of `x` up to `min_freq` and none of them work, then no such partition is possible, and we return `false`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        if (deck.length < 2) {
            return false;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int card : deck) {
            counts.put(card, counts.getOrDefault(card, 0) + 1);
        }

        int minFreq = Integer.MAX_VALUE;
        for (int count : counts.values()) {
            minFreq = Math.min(minFreq, count);
        }

        if (minFreq < 2) {
            return false;
        }

        for (int x = 2; x <= minFreq; x++) {
            boolean isDivisible = true;
            for (int count : counts.values()) {
                if (count % x != 0) {
                    isDivisible = false;
                    break;
                }
            }
            if (isDivisible) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Create a frequency map (e.g., a `HashMap`) to store the count of each card in the `deck`.
- Iterate through the `deck` to populate the frequency map.
- Find the minimum frequency, `min_freq`, among all the values in the map.
- If `min_freq` is less than 2, it's impossible to form groups of size `x > 1`, so return `false`.
- Iterate through all possible group sizes `x` from 2 up to `min_freq`.
- For each `x`, check if it divides every frequency in the map.
  - If `x` divides all frequencies, a valid partition is found. Return `true`.
  - If `x` fails to divide any frequency, it's not a valid group size, so continue to the next `x`.
- If the loop completes without finding a suitable `x`, return `false`.

## Greatest Common Divisor (GCD) Approach
A more efficient approach recognizes that the problem is equivalent to finding if there is a common divisor `x > 1` for all the card counts. This can be solved by calculating the greatest common divisor (GCD) of all the counts. If the GCD is greater than 1, a valid partition exists; otherwise, it does not.
**Time:** O(N + U * log(C_max)), where N is the number of cards, U is the number of unique cards, and C_max is the maximum frequency. O(N) is for counting frequencies. Then, we iterate through U counts, and each GCD operation takes O(log(C_max)) time. · **Space:** O(U), where U is the number of unique cards, to store the frequency map. In the worst case, U can be equal to N, so the space complexity is O(N).
**Pros:** Highly efficient and mathematically sound.; Provides an optimal time complexity for this problem.; Avoids the unnecessary iteration of the brute-force approach.
**Cons:** Requires knowledge of the Greatest Common Divisor (GCD) concept and the Euclidean algorithm for an efficient implementation.
### Explanation
This approach reframes the problem mathematically. If the deck can be partitioned into groups of size `x`, it means the count of each card type must be a multiple of `x`. In other words, `x` must be a common divisor of all the frequencies.

The problem asks if *any* such partition is possible for some `x > 1`. This is equivalent to asking if there exists a common divisor greater than 1 for all the frequencies. This condition is met if and only if the Greatest Common Divisor (GCD) of all the frequencies is greater than 1.

The algorithm is as follows:
1.  Count the frequencies of each card, for instance, using a hash map.
2.  Calculate the GCD of all these frequencies. This can be done iteratively. Initialize a result `g = 0`. Then, for each frequency `c`, update `g = gcd(g, c)`. The Euclidean algorithm provides an efficient way to compute `gcd(a, b)`. Note that `gcd(0, k) = k`, so this iterative approach works correctly.
3.  After finding the final GCD of all counts, if it's greater than 1, we can form groups of that size. So, we return `true`. If the GCD is 1, no common divisor greater than 1 exists, so we return `false`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    // Helper function to compute GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int card : deck) {
            counts.put(card, counts.getOrDefault(card, 0) + 1);
        }

        int resultGcd = 0;
        for (int count : counts.values()) {
            resultGcd = gcd(resultGcd, count);
        }

        return resultGcd > 1;
    }
}
```
### Algorithm
- Create a frequency map of the cards in `deck` by iterating through the array. This takes O(N) time.
- Initialize a variable, let's call it `g`, to 0. This variable will store the running GCD of the frequencies.
- Iterate through the values (frequencies) of the map.
- For each frequency `c`, update `g` by calculating the GCD of the current `g` and `c`. The `gcd(a, b)` can be computed efficiently using the Euclidean algorithm.
- After iterating through all frequencies, the final value of `g` will be the GCD of all card counts.
- The condition for a valid partition is that there must exist a group size `x > 1`. This is possible if and only if the GCD of all counts is greater than 1.
- Return `g > 1`.

# Solutions
### Java

```java
class Solution {
public
  boolean hasGroupsSizeX(int[] deck) {
    int[] cnt = new int[10000];
    for (int v : deck) {
      ++cnt[v];
    }
    int g = -1;
    for (int v : cnt) {
      if (v > 0) {
        g = g == -1 ? v : gcd(g, v);
      }
    }
    return g >= 2;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasGroupsSizeX(vector<int> &deck) {
    int cnt[10000] = {0};
    for (int &v : deck)
      ++cnt[v];
    int g = -1;
    for (int &v : cnt) {
      if (v) {
        g = g == -1 ? v : __gcd(g, v);
      }
    }
    return g >= 2;
  }
};

```

### Python

```python
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool: vals = Counter(deck). values() return reduce(gcd, vals) >= 2

```