914. X of a Kind in a Deck of Cards

1. Description

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.

2. Example

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.

3. Constraints

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

4. Solutions

GCD

n = deck.size(), C is the number range
Time complexity: O(nlogC)
Space complexity: O(n + C)

class Solution {
public:
    bool hasGroupsSizeX(const vector<int> &deck) {
        array<int, range_> count{0};
        for (auto num : deck) {
            ++count[num];
        }

        int result = count[deck[0]];
        for (int i = 1; i < deck.size(); ++i) {
            result = gcd(result, count[deck[i]]);
        }

        return result >= 2;
    }

private:
    const static int range_ = 10000;
};