X Of A Kind In A Deck Of Cards - Leetcode Solution

Problem:

Given a deck of cards, return true if and only if you can choose X cards from the deck so that group of X cards are of the same suit.

Example 1:

Input: deck = [1,2,3,4,4,3,2,1], X = 4 Output: true

Explanation: There are 4 suits: diamonds, clubs, hearts, spades. Since there are 4 cards with the same suit (diamonds), we can choose those 4 cards and return true.

Example 2:

Input: deck = [1,1,1,2,2,2,3,3], X = 3 Output: false

Explanation: There are 3 suits: diamonds, clubs, hearts, spades. The maximum number of cards with the same suit is 2. Therefore, we cannot choose 3 cards with the same suit.

Solution:

We can solve this problem using the concept of gcd (greatest common divisor). For this, we will count the frequency of each card in the deck, and then find the gcd of all the frequencies. If the gcd is greater than or equal to X, then we can choose X cards with the same suit, else we cannot.

Let's take an example to understand this approach:

Input: deck = [1,2,3,4,4,3,2,1], X = 4 Output: true

Step 1: Count the frequency of each card. freq = {1: 2, 2: 2, 3: 2, 4: 2}

Step 2: Find the gcd of all frequencies. gcd = 2

Step 3: Check if gcd is greater than or equal to X. gcd >= X, hence return true.

Implementation:

We can implement this approach using a hash table to count the frequency of each card, and the math.gcd() function to find the gcd of all frequencies.

Here is the Python code for the solution:

import collections
import math

class Solution:
    def hasGroupsSizeX(self, deck: List[int], X: int) -> bool:
        # Count the frequency of each card
        freq = collections.Counter(deck)
        
        # Find the gcd of all frequencies
        gcd = min(freq.values())
        for value in freq.values():
            gcd = math.gcd(gcd, value)
        
        # Check if gcd is greater than or equal to X
        return gcd >= X

Time Complexity:

The time complexity of this approach is O(N log N), where N is the number of cards in the deck. This is because we need to count the frequency of each card, which takes O(N) time, and find the gcd of all frequencies, which takes O(log N) time using the Euclidean algorithm.

Space Complexity:

The space complexity of this approach is O(N), where N is the number of cards in the deck. This is because we need to store the frequency of each card in a hash table.

1