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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
};