Skip to main content

X of a Kind in a Deck of Cards

Problem Description

You are given an integer array deck where deck[i] represents the number written on the ithi^th 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.

Examples

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

  • 1deck.length1041 \leq deck.length \leq 10^4
  • 0deck[i]<1040 \leq deck[i] < 10^4

Solution for X of a Kind in a Deck of Cards

Approach 1: Brute Force

Intuition

We can try every possible X.

Algorithm

Since we divide the deck of N cards into say, K piles of X cards each, we must have N % X == 0.

Then, say the deck has C_i copies of cards with number i. Each group with number i has X copies, so we must have C_i % X == 0. These are necessary and sufficient conditions.

Code in Different Languages

Written by @Shreyash3087
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
int N = deck.size();
vector<int> count(10000, 0);
for (int c : deck)
count[c]++;

vector<int> values;
for (int i = 0; i < 10000; ++i)
if (count[i] > 0)
values.push_back(count[i]);

for (int X = 2; X <= N; ++X) {
if (N % X == 0) {
bool valid = true;
for (int v : values) {
if (v % X != 0) {
valid = false;
break;
}
}
if (valid)
return true;
}
}

return false;
}
};


Complexity Analysis

Time Complexity: O(N2log(logN))O(N^2log(logN))

Reason: where N is the number of cards. It is outside the scope of this article to prove that the number of divisors of N is bounded by O(Nlog(logN))O(Nlog(⁡log⁡N)).

Space Complexity: O(N)O(N)

Reason: The space needed to store the counts of each card type in the values list.

Approach 2: Greatest Common Divisor

Intuition and Algorithm

Again, say there are C_i cards of number i. These must be broken down into piles of X cards each, ie. C_i % X == 0 for all i.

Thus, X must divide the greatest common divisor of C_i. If this greatest common divisor g is greater than 1, then X = g will satisfy. Otherwise, it won't.

Code in Different Languages

Written by @Shreyash3087
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
vector<int> count(10000, 0);
for (int c : deck)
count[c]++;

int g = -1;
for (int i = 0; i < 10000; ++i)
if (count[i] > 0) {
if (g == -1)
g = count[i];
else
g = gcd(g, count[i]);
}

return g >= 2;
}

int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
};

Complexity Analysis

Time Complexity: O(Nlog2(N))O(Nlog^2(N))

Reason: where N is the number of votes. If there are CiC_i cards with number i, then each gcd operation is naively O(log2Ci)O(\log^2 C_i). Better bounds exist, but are outside the scope of this article to develop

Space Complexity: O(N)O(N)

Reason: The space needed to store the counts of each card type in the values list.

Video Solution

References


Authors:

Loading...