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, orfalse otherwise.

Examples

Example 1

1
2
3

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

1
2
3

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

Solution

Method 1 – GCD of Counts

Intuition

If all card counts have a common divisor greater than 1, we can partition the deck into groups of that size. The problem reduces to checking if the greatest common divisor (GCD) of all card counts is at least 2.

Approach

  1. Count the frequency of each card value.
  2. Compute the GCD of all frequencies.
  3. If the GCD is at least 2, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func hasGroupsSizeX(deck []int) bool {
    cnt := map[int]int{}
    for _, x := range deck {
        cnt[x]++
    }
    ans := 0
    for _, v := range cnt {
        ans = gcd(ans, v)
    }
    return ans >= 2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : deck) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        int ans = 0;
        for (int v : cnt.values()) ans = gcd(ans, v);
        return ans >= 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

class Solution {
    fun hasGroupsSizeX(deck: IntArray): Boolean {
        val cnt = deck.groupingBy { it }.eachCount().values
        var ans = 0
        for (v in cnt) ans = gcd(ans, v)
        return ans >= 2
    }
    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}
1
2
3
4
5
6
7
8
9

from typing import List
from math import gcd
from functools import reduce
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        from collections import Counter
        vals = Counter(deck).values()
        ans = reduce(gcd, vals)
        return ans >= 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::collections::HashMap;
impl Solution {
    pub fn has_groups_size_x(deck: Vec<i32>) -> bool {
        let mut cnt = HashMap::new();
        for x in deck { *cnt.entry(x).or_insert(0) += 1; }
        let mut ans = 0;
        for &v in cnt.values() { ans = gcd(ans, v); }
        ans >= 2
    }
}
fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    hasGroupsSizeX(deck: number[]): boolean {
        const cnt: Record<number, number> = {};
        for (const x of deck) cnt[x] = (cnt[x] || 0) + 1;
        let ans = 0;
        const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
        for (const v of Object.values(cnt)) ans = gcd(ans, v);
        return ans >= 2;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Counting and GCD over all unique values, where n is the deck size.
  • 🧺 Space complexity: O(n) — For the frequency map.