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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

TrueFalse

I don’t know

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.

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

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

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

Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

914. X of a Kind in a Deck of Cards

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings