Skip to main content

914. X of a Kind in a Deck of Cards

easy

Decide whether a deck can be partitioned into groups of size >= 2 such that every group has the same value. The trick: compute the gcd of all the value-frequency counts.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array deck where deck[i] represents the number written on the i-th card. Partition the cards into one or more groups such that: Each group has exactly x cards where x > 1, and All the cards in one group have the same integer written on them. Return true if such partition is possible, or false otherwise.

Constraints

  • 1 <= deck.length <= 10^4
  • 0 <= deck[i] < 10^4

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count the frequency of each value in the deck.

Hint 2

For some valid group size x, every frequency must be divisible by x.

Hint 3

So an x >= 2 exists iff the gcd of all frequencies is >= 2.

Hint 4

Compute the gcd of all the frequency counts and check if it's >= 2.

Solution approach

Reveal approach

Step 1: count the frequency of each card value with a hash map. Step 2: compute g = gcd of all the frequency counts. Reduce across the counts pairwise: start with the first count, then g = gcd(g, next_count) for each subsequent count. Step 3: return g >= 2. Why it works: if a valid partition exists with group size x >= 2, then x divides every frequency count, so x divides their gcd, so g >= x >= 2. Conversely, if g >= 2, choose x = g and partition each value's cards into frequency / g groups of size g. O(n + k * log(max_freq)) where k is the number of distinct values, O(k) space for the counter.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • math
  • hash-table
  • euclidean-algorithm

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill X of a Kind in a Deck of Cards and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →