https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
Approach 2: Greatest Common Divisor
Time Complexity: , where is the number of votes. If there are cards with number , then each
https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/discuss/175845/C%2B%2BJavaPython-Greatest-Common-Divisor
X.
In a deck of cards, each card has an integer written on it.
Return
true
if and only if you can choose X >= 2
such that it is possible to split the entire deck into 1 or more groups of cards, where:- Each group has exactly
X
cards. - All the cards in each group have the same integer.
Example 1:
Input: [1,2,3,4,4,3,2,1] Output: true Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]
Example 2:
Input: [1,1,1,2,2,2,3,3] Output: false Explanation: No possible partition.
Approach 2: Greatest Common Divisor
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.
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
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;
}
public int gcd(int x, int y) {
return x == 0 ? y : gcd(y%x, x);
}
Time Complexity: , where is the number of votes. If there are cards with number , then each
gcd
operation is naively . Better bounds exist, but are outside the scope of this article to develop.https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/discuss/175845/C%2B%2BJavaPython-Greatest-Common-Divisor
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> count = new HashMap<>();
int res = 0;
for (int i : deck) count.put(i, count.getOrDefault(i, 0) + 1);
for (int i : count.values()) res = gcd(i, res);
return res > 1;
}
public int gcd(int a, int b) {
return b > 0 ? gcd(b, a % b) : a;
}
X.
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.
Time Complexity: , where is the number of cards. It is outside the scope of this article to prove that the number of divisors of is bounded by .
public boolean hasGroupsSizeX(int[] deck) {
int N = deck.length;
int[] count = new int[10000];
for (int c: deck)
count[c]++;
List<Integer> values = new ArrayList();
for (int i = 0; i < 10000; ++i)
if (count[i] > 0)
values.add(count[i]);
search: for (int X = 2; X <= N; ++X)
if (N % X == 0) {
for (int v: values)
if (v % X != 0)
continue search;
return true;
}
return false;
}