Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/952.html
952. Largest Component Size by Common Factor (Hard)
Given a non-empty array of unique positive integers A
, consider the following graph:
- There are
A.length
nodes, labelledA[0]
toA[A.length - 1];
- There is an edge between
A[i]
andA[j]
if and only ifA[i]
andA[j]
share a common factor greater than 1.
Return the size of the largest connected component in the graph.
Example 1:
Input: [4,6,15,35] Output: 4![]()
Example 2:
Input: [20,50,9,63] Output: 2![]()
Example 3:
Input: [2,3,6,7,4,12,21,39] Output: 8![]()
Note:
1 <= A.length <= 20000
1 <= A[i] <= 100000
Related Topics:
Math, Union Find
Solution 1. Union Find + Factor
The number of elements is big. Can we reduce the scale? Consider all the primes that are factors of numbers in A
.
For each number A[i]
, we union all the factors of A[i]
. In this way, A[i]
s are grouped according to factors. The size of the biggest group is the result.
// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
// Time: O(N * sqrt(W)) where N is length of A, W is max(A[i])
// Space: O(N)
class UnionFind {
vector<int> id;
public:
UnionFind(int N) : id(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
}
};
class Solution {
vector<int> factors(int n) {
vector<int> ans;
for (int i = 2; i * i <= n; ++i) {
if (n % i) continue;
ans.push_back(i);
while (n % i == 0) n /= i;
}
if (n > 1 || ans.empty()) ans.push_back(n);
return ans;
}
public:
int largestComponentSize(vector<int>& A) {
vector<vector<int>> F;
unordered_map<int, int> m;
int i = 0, ans = 0;
for (int n : A) {
auto f = factors(n);
F.push_back(f);
for (int x : f) {
if (!m.count(x)) m[x] = i++;
}
}
UnionFind uf(m.size());
for (auto &f : F) {
for (int x : f) uf.connect(m[f[0]], m[x]);
}
vector<int> cnt(m.size());
for (auto &f : F) ans = max(ans, ++cnt[uf.find(m[f[0]])]);
return ans;
}
};
-
class Solution { public int largestComponentSize(int[] A) { int max = 0; for (int num : A) max = Math.max(max, num); int[] parents = new int[max + 1]; for (int i = 0; i <= max; i++) parents[i] = i; for (int num : A) { int sqrt = (int) Math.sqrt(num); for (int i = 2; i <= sqrt; i++) { if (num % i == 0) { union(parents, num, i); union(parents, num, num / i); } } } int[] counts = new int[max + 1]; int maxSize = 0; for (int num : A) { int ancestor = find(parents, num); counts[ancestor]++; maxSize = Math.max(maxSize, counts[ancestor]); } return maxSize; } public void union(int[] parents, int num1, int num2) { int ancestor1 = find(parents, num1); int ancestor2 = find(parents, num2); if (ancestor1 != ancestor2) parents[ancestor1] = ancestor2; } public int find(int[] parents, int num) { while (parents[num] != num) { parents[num] = parents[parents[num]]; num = parents[num]; } return num; } } ############ class UnionFind { int[] p; UnionFind(int n) { p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } } void union(int a, int b) { int pa = find(a), pb = find(b); if (pa != pb) { p[pa] = pb; } } int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } class Solution { public int largestComponentSize(int[] nums) { int m = 0; for (int v : nums) { m = Math.max(m, v); } UnionFind uf = new UnionFind(m + 1); for (int v : nums) { int i = 2; while (i <= v / i) { if (v % i == 0) { uf.union(v, i); uf.union(v, v / i); } ++i; } } int[] cnt = new int[m + 1]; int ans = 0; for (int v : nums) { int t = uf.find(v); ++cnt[t]; ans = Math.max(ans, cnt[t]); } return ans; } }
-
// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/ // Time: O(N * sqrt(M)) // Space: O(N + sqrt(M)) class UnionFind { vector<int> id, size; public: UnionFind(int N) : id(N), size(N, 1) { iota(begin(id), end(id), 0); } int find(int a) { return id[a] == a ? a : (id[a] = find(id[a])); } void connect(int a, int b) { int p = find(a), q = find(b); if (p == q) return; id[p] = q; size[q] += size[p]; } int getSize(int a) { return size[find(a)]; } }; class Solution { vector<int> factors(int n) { vector<int> ans; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) ans.push_back(i); while (n % i == 0) n /= i; } if (n > 1) ans.push_back(n); return ans; } public: int largestComponentSize(vector<int>& A) { int N = A.size(), ans = 0; UnionFind uf(N); unordered_map<int, int> m; // primce factor -> a representative (the first) number with this factor for (int i = 0; i < N; ++i) { for (int &f : factors(A[i])) { if (m.count(f)) uf.connect(i, m[f]); else m[f] = i; } } for (int i = 0; i < N; ++i) ans = max(ans, uf.getSize(i)); return ans; } };
-
class UnionFind: def __init__(self, n): self.p = list(range(n)) def union(self, a, b): pa, pb = self.find(a), self.find(b) if pa != pb: self.p[pa] = pb def find(self, x): if self.p[x] != x: self.p[x] = self.find(self.p[x]) return self.p[x] class Solution: def largestComponentSize(self, nums: List[int]) -> int: uf = UnionFind(max(nums) + 1) for v in nums: i = 2 while i <= v // i: if v % i == 0: uf.union(v, i) uf.union(v, v // i) i += 1 return max(Counter(uf.find(v) for v in nums).values()) ############ class Solution: def largestComponentSize(self, A): """ :type A: List[int] :rtype: int """ ma = max(A) N = len(A) m = list(range(ma + 1)) for a in A: for k in range(2, int(math.sqrt(a)) + 1): if a % k == 0: self.u(m, a, k) self.u(m, a, a // k) count = collections.defaultdict(int) for a in A: count[self.f(m, a)] += 1 return max(count.values()) def f(self, m, a): while m[a] != a: m[a] = m[m[a]] a = m[a] return a def u(self, m, a, b): if m[a] == m[b]: return pa = self.f(m, a) pb = self.f(m, b) m[pa] = pb
-
func largestComponentSize(nums []int) int { m := 0 for _, v := range nums { m = max(m, v) } p := make([]int, m+1) for i := range p { p[i] = i } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } union := func(a, b int) { pa, pb := find(a), find(b) if pa != pb { p[pa] = pb } } for _, v := range nums { i := 2 for i <= v/i { if v%i == 0 { union(v, i) union(v, v/i) } i++ } } ans := 0 cnt := make([]int, m+1) for _, v := range nums { t := find(v) cnt[t]++ ans = max(ans, cnt[t]) } return ans } func max(a, b int) int { if a > b { return a } return b }