Algorithm


Problem Name: 914. X of a Kind in a Deck of Cards

You are given an integer array deck where deck[i] represents the number written on the ith 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.

 

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 <= 104
  • 0 <= deck[i] < 104

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map < int, int>m;
        int n = deck.size();
        for (int i = 0; i  <  n; ++i) {
            m[deck[i]]++;
        }
        int base = 0;
        for (auto& p: m) {
            base = gcd(p.second, base);
        }
        return base > 1;
    }
    
    int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
deck = [1,2,3,4,4,3,2,1]

Output

x
+
cmd
true

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public boolean hasGroupsSizeX(int[] deck) {
    Map map = new HashMap<>();
    int maxGroupCount = Integer.MIN_VALUE;
    for (int card : deck) {
      map.put(card, map.getOrDefault(card, 0) + 1);
      maxGroupCount = Math.max(maxGroupCount, map.get(card));
    }
    for (Integer key : map.keySet()) {
      if (map.get(key)  <  2) {
        return false;
      }
    }
    for (int i = 2; i  < = maxGroupCount; i++) {
      boolean allPaired = true;
      for (Integer key : map.keySet()) {
        if (map.get(key)  <  i) {
          return false;
        }
        if (map.get(key) % i != 0) {
          allPaired = false;
          break;
        }
      }
      if (allPaired) {
        return true;
      }
    }
    return false;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
deck = [1,2,3,4,4,3,2,1]

Output

x
+
cmd
true

#3 Code Example with Javascript Programming

Code - Javascript Programming


const hasGroupsSizeX = function(deck) {
  if(deck == null || deck.length <= 1) return false
  const hash = {}
  for(let e of deck) {
    if(hash[e] == null) hash[e] = 0
    hash[e]++
  }
  let res = 0
  for(let k in hash) res = gcd(hash[k], res>
  return res > 1
};

function gcd(a, b) {
  return b ? gcd(b, a % b) : a
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
deck = [1,1,1,2,2,2,3,3]

Output

x
+
cmd
false

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def hasGroupsSizeX(self, deck):
        import functools
        def gcd(a, b):
            if not b: return a
            return gcd(b, a % b)
        return functools.reduce(gcd, collections.Counter(deck).values()) != 1
Copy The Code & Try With Live Editor

Input

x
+
cmd
deck = [1,1,1,2,2,2,3,3]

Output

x
+
cmd
false

#5 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    public class _0914_XOfAKindInADeckOfCards
    {
        public bool HasGroupsSizeX(int[] deck)
        {
            var counts = new Dictionary < int, int>();
            foreach (var card in deck)
            {
                if (!counts.ContainsKey(card)) counts[card] = 1;
                else
                    counts[card]++;
            }

            var min = counts.Values.Min();
            for (var i = 2; i  < = min; i++)
            {
                foreach (var count in counts.Values)
                {
                    if (count % i != 0)
                        goto skip;
                }

                return true;
            skip:;
            }

            return false;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
deck = [1,2,3,4,4,3,2,1]

Output

x
+
cmd
true
Advertisements

Demonstration


Previous
#913 Leetcode Cat and Mouse Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#915 Leetcode Partition Array into Disjoint Intervals Solution in C, C++, Java, JavaScript, Python, C# Leetcode