Sponsored
Sponsored
This 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.
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.
1function gcd(a, b) {
2 while (b !== 0) {
3 const temp = b;
4 b = a % b;
5 a = temp;
6 }
7 return a;
8}
9
10function hasGroupsSizeX(deck) {
11 const freq = {};
12 for (const card of deck) {
13 if (!freq[card]) freq[card] = 0;
14 freq[card]++;
15 }
16
17 const values = Object.values(freq);
18 let X = values[0];
19 for (const count of values) {
20 X = gcd(X, count);
21 }
22
23 return X > 1;
24}
25
26console.log(hasGroupsSizeX([1,2,3,4,4,3,2,1]));This JavaScript solution uses an object to track the frequency of each card. It computes the GCD of the frequencies and verifies that it's greater than 1 to confirm valid group size.
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.
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.
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.