914. X of a Kind in a Deck of Cards

EasyArrayHash TableMathCountingNumber Theory

Problem Description

The problem presents us with an array named deck, where each element in the array represents a number on a card. We need to determine if it's possible to divide these cards into one or more groups such that two conditions are met:

Each group must contain the exact same number of cards, x, where x is greater than 1.
All cards within any given group must have the same number written on them.

If such a division is possible, we should return true. Otherwise, the function should return false.

Intuition

The intuition behind the solution is to use number frequency and the greatest common divisor (GCD). The key idea is that if all the card numbers' frequency counts have a GCD greater than 1, we can form groups that satisfy the problem's conditions.

Here's why this works:

Count the frequency of each number in the deck using a frequency counter (Counter(deck)). This tells us how many times each unique number appears in the deck.
The crucial insight is that if we can find a common group size x that divides evenly into all counts, we can create the groups required. In mathematical terms, x must be a common divisor for all frequencies. We then use reduce and gcd to calculate the GCD across all frequency counts.
If the GCD of these counts is at least 2, this means there is a common divisor for all frequencies, and hence we can partition the deck into groups of size GCD or any multiple of the GCD that is also a divisor of all frequencies. If the GCD is 1, this means there's no common divisor greater than 1, and it would be impossible to partition the deck as desired.

By following this reasoning, we arrive at the provided solution approach.

Learn more about Math patterns.

Solution Approach

The implementation makes use of Python's standard library, particularly the collections.Counter class to calculate the frequency of each card and the functools.reduce function in combination with [math](/problems/math-basics).gcd to find the greatest common divisor (GCD) of the card frequencies.

Here's a step-by-step explanation:

We create a frequency counter for the deck array with Counter(deck) that returns a dictionary with card values as keys and their respective frequencies as values.
We extract the values (frequencies) from the counter and store them in the variable vals using vals = Counter(deck).values().
The reduce function is used to apply the gcd (greatest common divisor) function repeatedly to the items of vals - effectively finding the GCD of all frequencies. The syntax reduce(gcd, vals) computes the GCD of the first two elements in vals, then the GCD of that result with the next element, and so on, until all elements are processed.
Finally, the GCD result is compared against the integer 2. If the GCD is greater than or equal to 2 (reduce(gcd, vals) >= 2), this means all card frequencies have a common divisor greater than 1. This allows them to be divided into groups satisfying the problem's constraints and thereby returning true. If the GCD is less than 2, it means there is no common divisor that can form the groups as required, and we return false.

The solution leverages the mathematical property that any common divisor of two numbers also divides their GCD. By finding the GCD of all frequency counts, we ensure that this number can be a valid group size for partitioning the deck accordingly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the array deck = [1,2,3,4,4,3,2,1,4,4].

First, we will count the frequency of each number using Counter(deck). Applying this to our deck gives us the count {1: 2, 2: 2, 3: 2, 4: 4}. The key-value pairs here represent the card number and its frequency, respectively.
Next step is to extract these frequencies into a list: vals = [2, 2, 2, 4]. These are the counts of cards 1, 2, 3, and 4 respectively.
Now we use the reduce function combined with the gcd function to find the GCD of all these frequency counts. For our example, the GCD of [2, 2, 2, 4] is 2. This is calculated by starting with the GCD of the first two elements: gcd(2, 2), which is 2. Then it continues by taking this result and applying the GCD with the next element: gcd(2, 2) -> 2, and finally gcd(2, 4) -> 2.
After figuring out that our GCD is 2, which is greater than or equal to 2, we can conclude that we can divide the deck into groups that meet both conditions mentioned. We have 1 pair, 2 pair, 3 pair, and two pairs of 4 which fits the criteria as each group (pair in this case) has the same number of cards, and all cards in each group have the same number.

Therefore, for this deck array [1,2,3,4,4,3,2,1,4,4], the answer to whether the division is possible is true.

Solution Implementation

1from collections import Counter
2from functools import reduce
3from math import gcd
4from typing import List
5
6class Solution:
7    def hasGroupsSizeX(self, deck: List[int]) -> bool:
8        # Count the occurence of each card value in the deck
9        card_count = Counter(deck).values()
10      
11        # Use the reduce function to find the greatest common divisor (GCD) among all counts
12        gcd_result = reduce(gcd, card_count)
13      
14        # Check if the GCD is at least 2 (which means there is a possible group size X that is divisible by all card counts)
15        return gcd_result >= 2
16

1class Solution {
2    // Determines if we can partition the deck into groups with the same size and each group having the same integer
3    public boolean hasGroupsSizeX(int[] deck) {
4        // Create an array to hold the frequency of each value
5        int[] count = new int[10000];
6        // Count the occurrences of each number in the deck
7        for (int num : deck) {
8            count[num]++;
9        }
10
11        // Variable to store the greatest common divisor of all counts
12        int gcdValue = -1;
13        // Calculate the GCD of all the frequencies
14        for (int frequency : count) {
15            if (frequency > 0) {
16                // If gcdValue is still -1, this is the first non-zero frequency found, so assign it directly
17                // Otherwise, get the GCD of the current gcdValue and the new frequency
18                gcdValue = gcdValue == -1 ? frequency : gcd(gcdValue, frequency);
19            }
20        }
21      
22        // Return true if the GCD of all frequencies is at least 2 (we can form groups of at least 2)
23        return gcdValue >= 2;
24    }
25
26    // Recursive method to calculate the greatest common divisor (GCD) of two numbers
27    private int gcd(int a, int b) {
28        // The GCD of b and the remainder of a divided by b. When b is 0, a is the GCD.
29        return b == 0 ? a : gcd(b, a % b);
30    }
31}
32

1#include<vector>
2#include<numeric> // For std::gcd (C++17 and above)
3
4class Solution {
5public:
6    bool hasGroupsSizeX(vector<int>& deck) {
7      
8        // Array to count the occurrences of each number in the deck
9        int counts[10000] = {0};
10        for (int& value : deck) {
11            // Increment the count for this number
12            counts[value]++;
13        }
14      
15        // Variable to store the greatest common divisor of all counts, 
16        // initial value -1 indicates that we haven't processed any count yet
17        int gcdOfCounts = -1;
18        for (int& count : counts) {
19            if (count) { // Checking if the count is not zero
20                if (gcdOfCounts == -1) {
21                    // This is the first non-zero count, we assign it to gcdOfCounts
22                    gcdOfCounts = count;
23                } else {
24                    // Calculate the GCD of the current gcdOfCounts and this count
25                    gcdOfCounts = std::gcd(gcdOfCounts, count);
26                }
27            }
28        }
29      
30        // A valid group size exists if the GCD of all counts is at least 2
31        return gcdOfCounts >= 2;
32    }
33};
34

1function gcd(a: number, b: number): number {
2  // Base case for recursion: If b is 0, gcd is a
3  if (b === 0) return a;
4  // Recursive case: gcd of b and the remainder of a divided by b
5  return gcd(b, a % b);
6}
7
8function hasGroupsSizeX(deck: number[]): boolean {
9  // Object to count the occurrences of each number in the deck
10  const counts: { [key: number]: number } = {};
11
12  // Count occurrences of each card
13  for (const value of deck) {
14    if (counts[value]) {
15      counts[value]++;
16    } else {
17      counts[value] = 1;
18    }
19  }
20
21  // Variable to store the greatest common divisor of all counts.
22  // Initial value -1 indicates that we haven't processed any count yet.
23  let gcdOfCounts = -1;
24
25  // Iterate over card counts to find gcd
26  for (const count of Object.values(counts)) {
27    if (count) { // Checking if the count is not zero
28      if (gcdOfCounts === -1) {
29        // This is the first non-zero count, we assign it to gcdOfCounts
30        gcdOfCounts = count;
31      } else {
32        // Calculate the GCD of the current gcdOfCounts and this count
33        gcdOfCounts = gcd(gcdOfCounts, count);
34      }
35    }
36  }
37
38  // A valid group size exists if the GCD of all counts is at least 2
39  return gcdOfCounts >= 2;
40}
41

Time and Space Complexity

Time Complexity

The time complexity of the code involves a few operations. First, the counting of elements using Counter, which takes O(n) time, where n is the number of cards in the deck. Secondly, reduce(gcd, vals) computes the Greatest Common Divisor (GCD) of the counts. Calculating the GCD using Euclid’s algorithm has a worst-case complexity of O(log(min(a, b))) for two numbers a and b. Since reduce applies gcd pair-wise to the values, the complexity in the worst case will be O(m * log(k)), where m is the number of unique cards in the deck and k is the smallest count of a unique card.

Overall, the time complexity is O(n + m * log(k)).

Space Complexity

The space complexity is O(m) due to the space used by the Counter to store the count of unique cards. m is the number of unique cards. The space used by the reduce operation is O(1) as it only needs space for the accumulator to store the ongoing GCD.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know