Algorithm
Problem Name: 914. X of a Kind in a Deck of Cards
You are given an integer array deck where deck[i] represents the number written on the ith card.
Partition the cards into one or more groups such that:
- Each group has exactly
xcards wherex > 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.
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:
1 <= deck.length <= 1040 <= deck[i] < 104
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map < int, int>m;
int n = deck.size();
for (int i = 0; i < n; ++i) {
m[deck[i]]++;
}
int base = 0;
for (auto& p: m) {
base = gcd(p.second, base);
}
return base > 1;
}
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map map = new HashMap<>();
int maxGroupCount = Integer.MIN_VALUE;
for (int card : deck) {
map.put(card, map.getOrDefault(card, 0) + 1);
maxGroupCount = Math.max(maxGroupCount, map.get(card));
}
for (Integer key : map.keySet()) {
if (map.get(key) < 2) {
return false;
}
}
for (int i = 2; i < = maxGroupCount; i++) {
boolean allPaired = true;
for (Integer key : map.keySet()) {
if (map.get(key) < i) {
return false;
}
if (map.get(key) % i != 0) {
allPaired = false;
break;
}
}
if (allPaired) {
return true;
}
}
return false;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const hasGroupsSizeX = function(deck) {
if(deck == null || deck.length <= 1) return false
const hash = {}
for(let e of deck) {
if(hash[e] == null) hash[e] = 0
hash[e]++
}
let res = 0
for(let k in hash) res = gcd(hash[k], res>
return res > 1
};
function gcd(a, b) {
return b ? gcd(b, a % b) : a
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def hasGroupsSizeX(self, deck):
import functools
def gcd(a, b):
if not b: return a
return gcd(b, a % b)
return functools.reduce(gcd, collections.Counter(deck).values()) != 1
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0914_XOfAKindInADeckOfCards
{
public bool HasGroupsSizeX(int[] deck)
{
var counts = new Dictionary < int, int>();
foreach (var card in deck)
{
if (!counts.ContainsKey(card)) counts[card] = 1;
else
counts[card]++;
}
var min = counts.Values.Min();
for (var i = 2; i < = min; i++)
{
foreach (var count in counts.Values)
{
if (count % i != 0)
goto skip;
}
return true;
skip:;
}
return false;
}
}
}
Input
Output