X of a Kind in a Deck of Cards

easy math gcd counting

Problem

You are given an integer array deck where deck[i] is the value written on the i-th card. Return true if and only if you can partition the cards into one or more groups such that each group has exactly the same number of cards X (with X ≥ 2) and every card in a group shows the same value.

Inputdeck = [1, 2, 3, 4, 4, 3, 2, 1]

Outputtrue

Each value appears exactly twice, so we can form four groups of size X = 2.

deck (comma-separated)

from collections import Counter
from math import gcd
from functools import reduce

def has_groups_size_x(deck):
    counts = Counter(deck).values()
    g = reduce(gcd, counts)
    return g >= 2

function hasGroupsSizeX(deck) {
  const counts = new Map();
  for (const c of deck) counts.set(c, (counts.get(c) || 0) + 1);
  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
  let g = 0;
  for (const v of counts.values()) g = gcd(g, v);
  return g >= 2;
}

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int c : deck) counts.merge(c, 1, Integer::sum);
        int g = 0;
        for (int v : counts.values()) g = gcd(g, v);
        return g >= 2;
    }
    private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

bool hasGroupsSizeX(vector<int>& deck) {
    unordered_map<int, int> counts;
    for (int c : deck) counts[c]++;
    int g = 0;
    for (auto& p : counts) g = std::gcd(g, p.second);
    return g >= 2;
}

Explanation

We want to split the deck into equal-sized groups of one value each, with group size X >= 2. The neat insight is that a valid group size X must evenly divide every value's frequency, so the question reduces to a single GCD check.

First we count how many times each card value appears. Then we take the greatest common divisor of all those frequencies. Any common divisor of the counts is a workable group size, and the GCD is the largest one.

If gcd >= 2, we can pick X = gcd (or any divisor of it that is at least 2) and partition every value's cards into equal groups, so the answer is true. If the GCD is 1, some value can only form groups of size 1, which is not allowed, so false.

Example: deck = [1, 2, 3, 4, 4, 3, 2, 1]. Every value appears twice, so the frequencies are all 2 and gcd = 2. Since 2 >= 2, we make four groups of size 2 → true.

It works because evenly grouping each value independently is possible exactly when one group size divides all the counts at once.

Time: O(n log V) Space: O(n)