#914 X of a Kind in a Deck of Cards - Solution

You are given an integer array deck where deck[i] represents the number written on the i^th card.

Partition the cards into one or more groups such that:

Each group has exactly x cards where x > 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 <= 10⁴
0 <= deck[i] < 10⁴

Approach	Time Complexity	Space Complexity
Hash Map Counting + GCD of Frequencies	O(n)	O(n)

Solutions (12)

Approach 1: Frequency Counting and GCD

This approach involves counting the frequency of each card number. Once we have the frequencies, the problem reduces to checking if there exists a number x greater than 1 that divides all these frequencies. This is efficiently achieved by calculating the GCD of the list of frequencies.

Time Complexity: O(n + m log m), where n is the length of the deck and m is the number of unique numbers.
Space Complexity: O(m), where m is the number of unique numbers due to the frequency array.

C C++Java Python C#JavaScript

1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6int gcd(int a, int b) {
7    return b == 0 ? a : gcd(b, a % b);
8}
9
10bool hasGroupsSizeX(std::vector<int>& deck) {
11    std::unordered_map<int, int> freq;
12    for (int num : deck) {
13        freq[num]++;
14    }

    int X = 0;
    for (auto entry : freq) {
        X = gcd(X, entry.second);
    }

    return X > 1;
}

int main() {
    std::vector<int> deck = {1,2,3,4,4,3,2,1};
    std::cout << (hasGroupsSizeX(deck) ? "true" : "false") << std::endl;
    return 0;
}

Explanation

This C++ solution uses a hash map to count frequencies and then computes the GCD of these frequencies. If the GCD is greater than 1, the solution is true.

Approach 2: Counting Elements and Checking Lowest Frequency

This approach also involves counting the frequency of each card in the deck. However, rather than immediately calculating the GCD, it sorts the frequency list and iteratively checks for the smallest divisor of these frequencies greater than 1.

Time Complexity: O(n + m√n), where n is the number of cards and m is the number of unique cards.
Space Complexity: O(m) for the frequency array.

C C++Java Python C#JavaScript

1#include <vector>
#include <unordered_map>
#include <algorithm>

bool hasGroupsSizeX(std::vector<int>& deck) {
    std::unordered_map<int, int> freq;
    for (int num : deck) {
        freq[num]++;
    }

    int min_freq = INT_MAX;
    for (auto& entry : freq) {
        if (entry.second < min_freq) {
            min_freq = entry.second;
        }
    }

    for (int x = 2; x <= min_freq; x++) {
        bool canDivide = true;
        for (auto& entry : freq) {
            if (entry.second % x != 0) {
                canDivide = false;
                break;
            }
        }
        if (canDivide) {
            return true;
        }
    }
    return false;
}

int main() {
    std::vector<int> deck = {1,1,1,2,2,2,3,3};
    std::cout << (hasGroupsSizeX(deck) ? "true" : "false") << std::endl;
    return 0;
}