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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private int 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
14 public bool HasGroupsSizeX(int[] deck) {
15 Dictionary<int, int> freq = new Dictionary<int, int>();
16 foreach (int num in deck) {
17 if (!freq.ContainsKey(num)) freq[num] = 0;
18 freq[num]++;
19 }
20
21 int X = 0;
22 foreach (int count in freq.Values) {
23 X = GCD(X, count);
24 }
25
26 return X > 1;
27 }
28
29 public static void Main() {
30 Solution sol = new Solution();
31 int[] deck = {1,2,3,4,4,3,2,1};
32 Console.WriteLine(sol.HasGroupsSizeX(deck) ? "true" : "false");
33 }
34}The C# implementation uses a `Dictionary` to store frequency counts. The calculation of GCD among these counts helps determine the possibility of the desired grouping.
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.
1using System.Collections.Generic;
public class Solution {
public bool HasGroupsSizeX(int[] deck) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in deck) {
if (!freq.ContainsKey(num)) freq[num] = 0;
freq[num]++;
}
int min_freq = int.MaxValue;
foreach (int count in freq.Values) {
if (count < min_freq) {
min_freq = count;
}
}
for (int x = 2; x <= min_freq; x++) {
bool canDivide = true;
foreach (int count in freq.Values) {
if (count % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
public static void Main() {
Solution sol = new Solution();
int[] deck = {1,1,1,2,2,2,3,3};
Console.WriteLine(sol.HasGroupsSizeX(deck) ? "true" : "false");
}
}In C#, the function calculates frequencies via a dictionary, examines each factor from 2 to the minimum frequency, and returns true if such a size is feasible.