Skip to content

914. X of a Kind in a Deck of Cards

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.

 

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

Solutions

Solution 1: Greatest Common Divisor

First, we use an array or hash table cnt to count the occurrence of each number. Only when \(X\) is a divisor of the greatest common divisor of all cnt[i], can it satisfy the problem's requirement.

Therefore, we find the greatest common divisor \(g\) of the occurrence of all numbers, and then check whether it is greater than or equal to \(2\).

The time complexity is \(O(n \times \log M)\), and the space complexity is \(O(n + \log M)\). Where \(n\) and \(M\) are the length of the array deck and the maximum value in the array deck, respectively.

1
2
3
4
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        cnt = Counter(deck)
        return reduce(gcd, cnt.values()) >= 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : deck) {
            cnt.merge(x, 1, Integer::sum);
        }
        int g = cnt.get(deck[0]);
        for (int x : cnt.values()) {
            g = gcd(g, x);
        }
        return g >= 2;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> cnt;
        for (int x : deck) {
            ++cnt[x];
        }
        int g = cnt[deck[0]];
        for (auto& [_, x] : cnt) {
            g = gcd(g, x);
        }
        return g >= 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func hasGroupsSizeX(deck []int) bool {
    cnt := map[int]int{}
    for _, x := range deck {
        cnt[x]++
    }
    g := cnt[deck[0]]
    for _, x := range cnt {
        g = gcd(g, x)
    }
    return g >= 2
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function hasGroupsSizeX(deck: number[]): boolean {
    const cnt: Record<number, number> = {};
    for (const x of deck) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
    let g = cnt[deck[0]];
    for (const [_, x] of Object.entries(cnt)) {
        g = gcd(g, x);
    }
    return g >= 2;
}

Comments