914. X of a Kind in a Deck of Cards

You are given an integer array deck where deck[i] represents the number written on the $i^{th}$ 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<=10^4$
• $0<=deck[i]<10^4$

From: LeetCode
Link: 914. X of a Kind in a Deck of Cards

---

Solution:

Ideas:

• If we partition into groups of equal size x>1 where each group has identical numbers, then every count must be divisible by x.

• Therefore x must divide the GCD of all counts. If that GCD ≥ 2, choose x = GCD. Otherwise, it’s impossible.

Code:

static int igcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

bool hasGroupsSizeX(int* deck, int deckSize) {
    if (deckSize < 2) return false;

    // deck[i] is in [0, 10000)
    int freq[10000] = {0};
    for (int i = 0; i < deckSize; ++i) {
        freq[deck[i]]++;
    }

    // Compute GCD of all non-zero frequencies
    int g = 0;
    for (int v = 0; v < 10000; ++v) {
        if (freq[v] > 0) {
            if (g == 0) g = freq[v];
            else        g = igcd(g, freq[v]);
            if (g == 1) return false; // early stop: cannot form groups of size >1
        }
    }
    return g >= 2;
}