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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4
5int gcd(int a, int b) {
6 while (b != 0) {
7 int temp = b;
8 b = a % b;
9 a = temp;
10 }
11 return a;
12}
13
14bool hasGroupsSizeX(int* deck, int deckSize) {
15 int freq[10000] = {0};
16
17 for (int i = 0; i < deckSize; i++) {
18 freq[deck[i]]++;
19 }
20
21 int X = 0;
22 for (int i = 0; i < 10000; i++) {
23 if (freq[i] > 0) {
24 if (X == 0) {
25 X = freq[i];
26 } else {
27 X = gcd(X, freq[i]);
28 }
29 }
30 }
31
32 return X > 1;
33}
34
35int main() {
36 int deck[] = {1,2,3,4,4,3,2,1};
37 int deckSize = sizeof(deck)/sizeof(deck[0]);
38 printf("%s\n", hasGroupsSizeX(deck, deckSize) ? "true" : "false");
39 return 0;
40}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.
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.
1#include <vector>
#include <unordered_map>
#include <algorithm>
bool hasGroupsSizeX(std::vector<int>& deck) {
std::unordered_map<int, int> freq;
for (int num : deck) {
freq[num]++;
}
int min_freq = INT_MAX;
for (auto& entry : freq) {
if (entry.second < min_freq) {
min_freq = entry.second;
}
}
for (int x = 2; x <= min_freq; x++) {
bool canDivide = true;
for (auto& entry : freq) {
if (entry.second % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
int main() {
std::vector<int> deck = {1,1,1,2,2,2,3,3};
std::cout << (hasGroupsSizeX(deck) ? "true" : "false") << std::endl;
return 0;
}Similarly to the previous implementation, this C++ function calculates frequency and attempts division by numbers ranging from 2 up to the smallest frequency, returning true if feasible.