Leetcode 914. X of a Kind in a Deck of Cards
Problem
The problem is about finding whether we can partition an array of integers into groups. The constraints for partitioning the array are as follows:
- Each group contains exactly
X
(> 2) cards. - All the cards in each group have the same integer.
We are given a deck of cards with each card containing an integer. We need to return True
if we can choose a group size X
that meets the above conditions. Otherwise, we return False
.
Example
Let's consider the array [1, 2, 3, 4, 4, 3, 2, 1] as an example. The possible partition can be [1, 1], [2, 2], [3, 3], [4, 4], where each group contains exactly two cards and all cards in the group have the same integer. Thus, the output for this example will be True
.
Approach
The approach to solving this problem is to use the properties of the greatest common divisor (GCD). The problem can be solved if the GCD of the counts of all the integers in the array is greater than or equal to 2.
We start by counting the occurrences of each integer in the array using a hash map. Then, we find the GCD of these counts. If the GCD is greater than or equal to 2, we return True
. Otherwise, we return False
.
Solution in Python
1 2python 3from collections import Counter 4from math import gcd 5from functools import reduce 6 7class Solution: 8 def hasGroupsSizeX(self, deck): 9 # count the occurrences of each integer 10 counts = Counter(deck).values() 11 # find the gcd of these counts 12 gcd_value = reduce(gcd, counts) 13 # return true if gcd is greater than or equal to 2, else false 14 return gcd_value >= 2
Solution in Java
1
2java
3import java.util.HashMap;
4import java.util.Map;
5
6public class Solution {
7 public boolean hasGroupsSizeX(int[] deck) {
8 Map<Integer, Integer> count = new HashMap<>();
9 int gcd = 0;
10
11 // count the occurrences of each integer
12 for (int num : deck) {
13 count.put(num, count.getOrDefault(num, 0) + 1);
14 }
15
16 // find the gcd of these counts
17 for (int value : count.values()) {
18 gcd = gcd(gcd, value);
19 }
20
21 // return true if gcd is greater than or equal to 2, else false
22 return gcd >= 2;
23 }
24
25 private int gcd(int a, int b) {
26 if (b == 0) {
27 return a;
28 } else {
29 return gcd(b, a % b);
30 }
31 }
32}
Solution in JavaScript
1
2javascript
3var hasGroupsSizeX = function(deck) {
4 let count = {};
5 let gcd = 0;
6
7 // count the occurrences of each integer
8 for (let num of deck) {
9 count[num] = (count[num] || 0) + 1;
10 }
11
12 // find the gcd of these counts
13 for (let value in count) {
14 gcd = gcd(gcd, count[value]);
15 }
16
17 // return true if gcd is greater than or equal to 2, else false
18 return gcd >= 2;
19
20 function gcd(a, b) {
21 if (b === 0) {
22 return a;
23 } else {
24 return gcd(b, a % b);
25 }
26 }
27};
Solution in C++
1
2cpp
3#include <unordered_map>
4#include <algorithm>
5
6class Solution {
7public:
8 bool hasGroupsSizeX(std::vector<int>& deck) {
9 std::unordered_map<int, int> count;
10 int gcd = 0;
11
12 // count the occurrences of each integer
13 for (int num : deck) {
14 ++count[num];
15 }
16
17 // find the gcd of these counts
18 for (auto const &pair : count) {
19 gcd = std::__gcd(gcd, pair.second);
20 }
21
22 // return true if gcd is greater than or equal to 2, else false
23 return gcd >= 2;
24 }
25};
Solution in C#
1
2csharp
3using System.Collections.Generic;
4using System.Linq;
5
6public class Solution {
7 public bool HasGroupsSizeX(int[] deck) {
8 Dictionary<int, int> count = new Dictionary<int, int>();
9 int gcd = 0;
10
11 // count the occurrences of each integer
12 foreach (int num in deck) {
13 if (count.ContainsKey(num)) {
14 count[num]++;
15 } else {
16 count[num] = 1;
17 }
18 }
19
20 // find the gcd of these counts
21 foreach (int value in count.Values) {
22 gcd = Gcd(gcd, value);
23 }
24
25 // return true if gcd is greater than or equal to 2, else false
26 return gcd >= 2;
27 }
28
29 private int Gcd(int a, int b) {
30 if (b == 0) {
31 return a;
32 } else {
33 return Gcd(b, a % b);
34 }
35 }
36}
In Ruby:
1
2ruby
3def has_group_size_x(deck)
4 counts = deck.tally.values
5 return counts.min >= 2
6end
In Swift:
1
2swift
3func hasGroupsSizeX(_ deck: [Int]) -> Bool {
4 var counts = [Int: Int]()
5 for card in deck {
6 counts[card, default: 0] += 1
7 }
8 let minCount = counts.values.min()!
9 return minCount >= 2
10}
In Kotlin:
1
2kotlin
3fun hasGroupsSizeX(deck: IntArray): Boolean {
4 val count = mutableMapOf<Int, Int>()
5 for (num in deck) {
6 count[num] = count.getOrDefault(num, 0) + 1
7 }
8 val gcd = count.values.reduce { a, b -> gcd(a, b) }
9 return gcd >= 2
10}
11
12private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
In Golang:
1
2go
3func hasGroupsSizeX(deck []int) bool {
4 counts := make(map[int]int)
5 for _, card := range deck {
6 counts[card]++
7 }
8
9 var minCount = len(deck)
10 for _, count := range counts {
11 minCount = min(minCount, count)
12 }
13
14 return minCount >= 2
15}
16
17func min(a, b int) int {
18 if a < b {
19 return a
20 }
21 return b
22}
As can be seen, the solution has been implemented in a variety of popular programming languages including Python, Java, JavaScript, C++, C#, Ruby, Swift, Kotlin, and Golang. The solution works by first counting the number of times each integer appears in the provided array. Then, it checks whether the smallest count is greater than or equal to 2 which will determine if we can form valid groups. If it is, we return true
; otherwise, we return false
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.