X Of A Kind In A Deck Of Cards

Problem Statement

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

Java Implementation

Java Approach Using Count Array Method

Output:

Code Explanation:

• The hasGroupsSizeX method checks if it's possible to form groups of cards in a deck, each with the same number of cards. It utilizes an array (count) to record the frequency of each card. The GCD method calculates the greatest common divisor (GCD) of two numbers.
• The algorithm iterates through the frequencies, updating the GCD dynamically. If the final GCD is greater than or equal to 2, it implies that cards can be grouped into sets of at least size 2. The solution ensures that each group has a common divisor, facilitating equal-sized grouping

Time Complexity:

• N is the number of cards in the deck, and time complexity equals O(N). The GCD calculation is carried out in a loop and takes O(logmin (a, b)) time for the inputs to be given.

Space Complexity:

• The space complexity is of order 1 because the required memory to store everything has a constant size. The algorithm applies a constant size count array of length 1000 to establish the frequency for each card, and the gcd function uses only a linear amount of space.

Java Approach Using HashMap

Output:

Code Explanation:

• The An algorithm in Java provides an answer to whether an array is divisible into groups with individual sizes of more than 1. The hasGroupsSizeX method constantly encompasses the hashMap for storing the frequency of every element. It does that by calculating the greatest common divisor (GCD) of these frequencies using the hcf, followed by an algorithm for best fit.
• The GCD shows how many people - the largest number - could belong to the group. If the GCD is greater than or equal to 2, that means that there is a group size, therefore, the method returns true, but if it is less than 2, then it returns false.

Time Complexity:

• The hasGroupsSizeXs organizational operations take constant time, O(N) with the size of arr being N.

Space Complexity:

• With space being O(N) as well. It uses hashmap that stores freq difference of every element and the size of the array A is the space added to it.