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:

1. Each group contains exactly X (> 2) cards.
2. 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.