Leetcode: X of a Kind in a Deck of Cards

X of a Kind in a Deck of Cards



Similar Problems:


In a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

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

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:

  1. 1 <= deck.length <= 10000
  2. 0 <= deck[i] < 10000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution: hashmap
// Blog link: https://code.dennyzhang.com/x-of-a-kind-in-a-deck-of-cards
// Basic Ideas: hashmap
// Complexity: Time O(n), Space O(n)
func gcd(x int, y int) int {
    if x == 0 { return y }
    for y!=0 {
        x, y = y, x%y
    }
    return x
}

func hasGroupsSizeX(deck []int) bool {
    m := map[int]int{}
    mincnt := 10000
    for _, d := range deck { m[d]++ }
    for _,v := range m {
        if v < mincnt { mincnt = v }
    }
    if mincnt == 1 { return false }
    for _,v:= range m {
        if gcd(v, mincnt) == 1 { return false }
    }
    return true
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.