X of a Kind in a Deck of Cards

Easy
484.

X of a Kind in a Deck of Cards

X of a Kind in a Deck of Cards is an easy coding problem on arrays, math and number theory, asked in Amazon and Google interviews.

You are given a deck of cards where deck[i] is the number written on the i-th card.

Return true if the whole deck can be split into groups such that every group has the same size x >= 2 and all cards in a group carry the same number.

Example 1

Input
deck = [1,2,3,4,4,3,2,1]
Output
true
Explanation
Every number appears twice, so x = 2 works.

Example 2

Input
deck = [1,1,1,2,2,2,3,3]
Output
false
Explanation
3 appears twice but 1 and 2 appear three times.

Example 3

Input
deck = [1,1,2,2,2,2]
Output
true
Explanation
x = 2 gives [1,1], [2,2] and [2,2].

Constraints

  • 1 <= deck.length <= 10000
  • 0 <= deck[i] < 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

X of a Kind in a Deck of Cards — Problem & Solution

X of a Kind in a Deck of Cards solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

X of a Kind in a Deck of Cards is an easy coding problem on arrays, math and number theory, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Number Theory
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a deck of cards where deck[i] is the number written on the i-th card.

Return true if the whole deck can be split into groups such that every group has the same size x >= 2 and all cards in a group carry the same number.

Example 1

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Every number appears twice, so x = 2 works.

Example 2

Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: 3 appears twice but 1 and 2 appear three times.

Example 3

Input: deck = [1,1,2,2,2,2]
Output: true
Explanation: x = 2 gives [1,1], [2,2] and [2,2].

Constraints

  • 1 <= deck.length <= 10000
  • 0 <= deck[i] < 10000

Hints for X of a Kind in a Deck of Cards

  1. Hint 1

    Group size x must divide the count of every distinct number.

  2. Hint 2

    A number that divides all the counts is a common divisor of them.

  3. Hint 3

    So the question is simply whether the greatest common divisor of all counts is at least 2.

How to solve X of a Kind in a Deck of Cards

If groups all have size x and each group is single-valued, then x divides the frequency of every distinct card. Such an x >= 2 exists exactly when the gcd of all frequencies is at least 2.

Approach

  1. Count how many times each distinct number appears.
  2. Fold the counts together with gcd, starting from 0 (since gcd(0, n) = n).
  3. Return true when the final gcd is >= 2.

Why it works

Any valid x is a common divisor of the frequencies, so x <= gcd. Conversely the gcd itself is a valid group size — each frequency is a multiple of it, so every number splits evenly into groups of that size.

Complexity

  • Time — O(n log C) where C is the largest frequency
  • Space — O(n)

Pitfalls

  • Checking only x = 2 misses decks where every count is 3.
  • A single card (deck = [1]) has gcd 1, so the answer is false — there is no group size >= 2.
  • Seeding the fold with the first count instead of 0 works too, but seeding with 1 collapses every answer to false.

Reference solution

Python

from typing import List

def hasGroupsSizeX(deck: List[int]) -> bool:
    from math import gcd
    count = {}
    for x in deck:
        count[x] = count.get(x, 0) + 1
    g = 0
    for c in count.values():
        g = gcd(g, c)
    return g >= 2

Java

public static boolean hasGroupsSizeX(int[] deck) {
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int x : deck) count.put(x, count.getOrDefault(x, 0) + 1);
    int g = 0;
    for (int c : count.values()) {
        int a = g, b = c;
        while (b != 0) { int t = a % b; a = b; b = t; }
        g = a;
    }
    return g >= 2;
}

C++

bool hasGroupsSizeX(vector<int>& deck) {
    unordered_map<int, int> count;
    for (int x : deck) count[x]++;
    int g = 0;
    for (auto& e : count) {
        int a = g, b = e.second;
        while (b != 0) { int t = a % b; a = b; b = t; }
        g = a;
    }
    return g >= 2;
}

JavaScript

var hasGroupsSizeX = function(deck) {
    function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
    const count = {};
    for (let i = 0; i < deck.length; i++) {
        const key = String(deck[i]);
        count[key] = (count[key] || 0) + 1;
    }
    let g = 0;
    const keys = Object.keys(count);
    for (let i = 0; i < keys.length; i++) g = gcd(g, count[keys[i]]);
    return g >= 2;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays