X of a Kind in a Deck of Cards

Problem Statement

In this task, you are provided with an array named deck, where each element deck[i] corresponds to the number on the i-th card. The challenge is to determine whether the cards can be organized into one or more groups meeting the following conditions:

• Each group should contain the same number of cards, specifically more than one card.
• All the cards in a group should have the same number.

The function should return true if such a partition is possible and false otherwise. This involves checking for the frequencies of each card and analyzing if these frequencies can be organized into groups where each group contains the same number of identical cards.

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

• 1 <= deck.length <= 10⁴
• 0 <= deck[i] < 10⁴

Approach and Intuition

• The primary step involves counting the frequency of each unique card value present in the deck using a hash map or a similar data structure.
• After constructing the frequency map, the challenge reduces to determining if the counts of cards (values in the frequency map) can be grouped with the same size, which should be greater than one.
• The mathematical approach to solve this is to find the greatest common divisor (GCD) of the count of cards. If the GCD is greater than 1, it implies that it is possible to split these frequencies into equal groups, satisfying the given conditions.

Step-by-step Approach

1. Initialize the Frequency Counter: Use a hash map or collections.Counter to store the frequency of each number in the deck.

2. Compute the GCD of All Frequencies: Iterate through the values in the frequency counter and compute the cumulative GCD.

3. Check the Final GCD Value: If the GCD is greater than 1, a valid partition is possible. Otherwise, return false.

Intuitive Explanation

• The potential to partition the deck into groups depends on the common factors between the counts of different card values.
• If the counts share a common divisor greater than 1, you can divide them into equal groups of that size.
• Example: If counts are 4 and 6, GCD is 2 → valid group size is 2 → possible partition. If counts are 3 and 5, GCD is 1 → cannot make valid partitions → return false.

Solutions

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int[] occurrences = new int[10000];
        for (int card: deck)
            occurrences[card]++;
    
        int groupgcd = -1;
        for (int j = 0; j < 10000; ++j)
            if (occurrences[j] > 0) {
                if (groupgcd == -1)
                    groupgcd = occurrences[j];
                else
                    groupgcd = computeGCD(groupgcd, occurrences[j]);
            }
    
        return groupgcd >= 2;
    }
    
    public int computeGCD(int a, int b) {
        return a == 0 ? b : computeGCD(b % a, a);
    }
}