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 <= 100000 <= deck[i] < 10000
Hints for X of a Kind in a Deck of Cards
Hint 1
Group size
xmust divide the count of every distinct number.Hint 2
A number that divides all the counts is a common divisor of them.
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
- Count how many times each distinct number appears.
- Fold the counts together with
gcd, starting from0(sincegcd(0, n) = n). - Return
truewhen 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 = 2misses decks where every count is 3. - A single card (
deck = [1]) has gcd 1, so the answer isfalse— there is no group size>= 2. - Seeding the fold with the first count instead of
0works too, but seeding with1collapses every answer tofalse.
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 >= 2Java
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