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:
x cards where x > 1, andReturn 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 <= 1040 <= deck[i] < 104This approach involves counting the frequency of each card number. Once we have the frequencies, the problem reduces to checking if there exists a number x greater than 1 that divides all these frequencies. This is efficiently achieved by calculating the GCD of the list of frequencies.
This C solution first counts the frequency of each number in the deck using an array. It then calculates the GCD of these frequencies. If the GCD is greater than 1, it returns true, otherwise false.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m log m), where n is the length of the deck and m is the number of unique numbers.
Space Complexity: O(m), where m is the number of unique numbers due to the frequency array.
This approach also involves counting the frequency of each card in the deck. However, rather than immediately calculating the GCD, it sorts the frequency list and iteratively checks for the smallest divisor of these frequencies greater than 1.
This solution starts by counting frequencies and finding the smallest non-zero frequency. It attempts to divide all frequencies by each integer from 2 to `min_freq`. If successful, it returns true; otherwise, returns false.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m√n), where n is the number of cards and m is the number of unique cards.
Space Complexity: O(m) for the frequency array.
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting and GCD | Time Complexity: O(n + m log m), where n is the length of the deck and m is the number of unique numbers. |
| Approach 2: Counting Elements and Checking Lowest Frequency | Time Complexity: O(n + m√n), where n is the number of cards and m is the number of unique cards. |
Big O explained with a deck of cards • Fireship • 1,309,101 views views
Watch 9 more video solutions →Practice X of a Kind in a Deck of Cards with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor