Divide the Array into Group of Integers with Size using GCD Algorithm


X of a Kind in a Deck of Cards

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: 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.

Example 3:
Input: deck = [1]
Output: false
Explanation: No possible partition.

Example 4:
Input: deck = [1,1]
Output: true
Explanation: Possible partition [1,1].

Example 5:
Input: deck = [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2].

Divide Group of Size X with Greatest Common Divisor Algorithm

First, we can use the Counter object to store the elements and the frequencies as they appear in the array. To be able to divide into equal group of size X where X is at least two, we can compute the GCD (Greatest Common Divisor) of all the frequencies. If the result is larger than 1, we then can accompolish this. For example, [2, 2, 2, 2, 1, 1].

1
2
3
4
5
6
7
8
9
from fractions import gcd
 
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        d = Counter(deck)
        x = min(d.values())
        for a, b in d.items():
            x = gcd(x, b)
        return x > 1
from fractions import gcd

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        d = Counter(deck)
        x = min(d.values())
        for a, b in d.items():
            x = gcd(x, b)
        return x > 1

We can use the reduce function to shorten the implementation.

1
2
3
4
5
6
from fractions import gcd
 
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        d = Counter(deck)
        return reduce(gcd, d.values()) > 1
from fractions import gcd

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        d = Counter(deck)
        return reduce(gcd, d.values()) > 1

Time complexity is O(NLog^2N) and space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
362 words
Last Post: Teaching Kids Programming - Using Hash Set or Hash Table to Count Next Element
Next Post: How to Sort List by Hamming Weight in C++?

The Permanent URL is: Divide the Array into Group of Integers with Size using GCD Algorithm

Leave a Reply