algoadvance

You are given an array deck where deck[i] represents the number written on the i-th card. Your task is to check if you can group the deck into 1 or more groups, where:

1. Each group has X cards.
2. All the cards in each group have the same integer.

Return True if you can do this and False otherwise.

Example:

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^4
• 0 <= deck[i] < 10^4

Clarifying Questions:

1. Can cards in the deck have the same number?
   • Yes, cards can have the same number.
2. Do all groups need to be of the same size X?
   • Yes, all groups should have the same size X.
3. Are there any constraints on the value of X?
   • X should be at least 2 (as single cards can’t form a group).

Strategy:

1. Count Frequency: First, count the frequency of each number in the deck.

2. Find Greatest Common Divisor (GCD): The key invariant here is the greatest common divisor (GCD) of the counts. We need the GCD of the counts to be at least 2. This is because if the GCD is X, then we can group the deck into X groups of cards with the same numbers.

   • Compute the frequency of each unique number in the deck using a Counter.
   • Find the GCD of these frequencies.
   • Check if the GCD is greater than or equal to 2.

Code:

from collections import Counter
from math import gcd
from functools import reduce

def hasGroupsSizeX(deck):
    # Count frequency of each number
    count = Counter(deck)
    # Get all frequency values
    freq_values = list(count.values())
    
    # Compute the GCD of all frequency values
    gcd_of_all = reduce(gcd, freq_values)
    
    # Return true if the GCD is at least 2
    return gcd_of_all >= 2

# Example usage:
example_deck1 = [1,2,3,4,4,3,2,1]
example_deck2 = [1,1,1,2,2,2,3,3]
print(hasGroupsSizeX(example_deck1)) # Output: True
print(hasGroupsSizeX(example_deck2)) # Output: False

Time Complexity:

• Counting Frequencies: O(n), where n is the length of the deck.
• Calculating GCD: This involves iterating through the list of counts and applying the reduce function with GCD, which is approximately O(k) for k unique integers in the deck.

So, overall time complexity is O(n + k) which simplifies close to O(n) when the number of unique integers is small relative to the size of the deck.

Try our interview co-pilot at AlgoAdvance.com

• 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?