algoadvance

Leetcode 914. X of a Kind in a Deck of Cards

Problem Statement

Given an array of integers deck, where deck[i] represents the ith card in the deck. Determine if we can partition the deck into one or more groups of cards, where:

• Each group has exactly X cards.
• All the cards in each group have the same integer value.

Return true if and only if such a partition is possible.

Example:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1], [2,2], [3,3], [4,4]

Clarifying Questions

1. Can the deck contain negative numbers?
   • No, the problem assumes the deck contains only non-negative integers.
2. Is the input always a valid list of integers?
   • Yes, the input can be assumed to be a valid list of integers.
3. Is there a maximum size for the deck array?
   • This isn’t specified, but it can be assumed that the input size can be reasonably handled within typical memory limits (e.g., not exceeding the range of typical array sizes in competitive programming).

Strategy

1. Frequency Counting: Count the frequency of each card in the deck using a hash map or dictionary.
2. Greatest Common Divisor (GCD): Find the GCD of these frequencies. This will help determine if there exists a common factor X that can divide all the frequencies perfectly, implying that the deck can be split into groups as required.
3. Check Result: If the GCD of the frequencies is greater than or equal to 2, return true; otherwise, return false.

Steps:

1. Count the frequency of each card in the deck.
2. Calculate the GCD of these frequencies.
3. If the GCD is at least 2, return true; otherwise, return false.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <numeric>

class Solution {
public:
    bool hasGroupsSizeX(std::vector<int>& deck) {
        std::unordered_map<int, int> count;
        for (int card : deck) {
            count[card]++;
        }
        
        int gcd = -1;
        for (auto& kv : count) {
            if (gcd == -1) {
                gcd = kv.second;
            } else {
                gcd = std::gcd(gcd, kv.second);
            }
        }
        
        return gcd >= 2;
    }
};

Time Complexity

• Counting Frequencies: O(N), where N is the number of cards in the deck.
• Calculating GCD: O(K * log M), where K is the number of unique cards (keys in the hash map) and M is the maximum frequency value.

Overall, the time complexity is: [ O(N + K \log M) ]

• Space Complexity: O(K), for storing the frequencies of unique cards.

This solution efficiently handles the problem constraints using standard algorithms for counting and computing the GCD.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?