from collections import defaultdict
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1]*n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
class Solution:
def largestComponentSize(self, nums):
n = len(nums)
uf = UnionFind(n)
factor_map = {}
def get_factors(x):
factors = set()
i = 2
while i*i <= x:
if x % i == 0:
factors.add(i)
while x % i == 0:
x //= i
i += 1
if x > 1:
factors.add(x)
return factors
for i, num in enumerate(nums):
for f in get_factors(num):
if f in factor_map:
uf.union(i, factor_map[f])
else:
factor_map[f] = i
count = defaultdict(int)
for i in range(n):
root = uf.find(i)
count[root] += 1
return max(count.values())
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
class UnionFind {
public:
vector<int> parent, size;
UnionFind(int n) : parent(n), size(n, 1) {
for(int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if(parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if(px == py) return;
if(size[px] < size[py]) swap(px, py);
parent[py] = px;
size[px] += size[py];
}
};
class Solution {
public:
vector<int> get_factors(int x) {
vector<int> res;
for(int i = 2; i*i <= x; ++i) {
if(x % i == 0) {
res.push_back(i);
while(x % i == 0) x /= i;
}
}
if(x > 1) res.push_back(x);
return res;
}
int largestComponentSize(vector<int>& nums) {
int n = nums.size();
UnionFind uf(n);
unordered_map<int, int> factor_map;
for(int i = 0; i < n; ++i) {
vector<int> factors = get_factors(nums[i]);
for(int f : factors) {
if(factor_map.count(f))
uf.unite(i, factor_map[f]);
else
factor_map[f] = i;
}
}
unordered_map<int, int> count;
int res = 0;
for(int i = 0; i < n; ++i) {
int root = uf.find(i);
count[root]++;
res = max(res, count[root]);
}
return res;
}
};
import java.util.*;
class UnionFind {
int[] parent, size;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
for(int i = 0; i < n; ++i) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if(parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int px = find(x), py = find(y);
if(px == py) return;
if(size[px] < size[py]) {
int tmp = px; px = py; py = tmp;
}
parent[py] = px;
size[px] += size[py];
}
}
class Solution {
private List<Integer> getFactors(int x) {
List<Integer> res = new ArrayList<>();
for(int i = 2; i * i <= x; ++i) {
if(x % i == 0) {
res.add(i);
while(x % i == 0) x /= i;
}
}
if(x > 1) res.add(x);
return res;
}
public int largestComponentSize(int[] nums) {
int n = nums.length;
UnionFind uf = new UnionFind(n);
Map<Integer, Integer> factorMap = new HashMap<>();
for(int i = 0; i < n; ++i) {
for(int f : getFactors(nums[i])) {
if(factorMap.containsKey(f))
uf.union(i, factorMap.get(f));
else
factorMap.put(f, i);
}
}
Map<Integer, Integer> count = new HashMap<>();
int res = 0;
for(int i = 0; i < n; ++i) {
int root = uf.find(i);
count.put(root, count.getOrDefault(root, 0) + 1);
res = Math.max(res, count.get(root));
}
return res;
}
}
class UnionFind {
constructor(n) {
this.parent = Array(n).fill(0).map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x) {
if(this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let px = this.find(x), py = this.find(y);
if(px === py) return;
if(this.size[px] < this.size[py]) [px, py] = [py, px];
this.parent[py] = px;
this.size[px] += this.size[py];
}
}
function getFactors(x) {
const res = new Set();
let i = 2;
while(i * i <= x) {
if(x % i === 0) {
res.add(i);
while(x % i === 0) x = Math.floor(x / i);
}
i++;
}
if(x > 1) res.add(x);
return Array.from(res);
}
var largestComponentSize = function(nums) {
const n = nums.length;
const uf = new UnionFind(n);
const factorMap = new Map();
for(let i = 0; i < n; ++i) {
for(const f of getFactors(nums[i])) {
if(factorMap.has(f))
uf.union(i, factorMap.get(f));
else
factorMap.set(f, i);
}
}
const count = new Map();
let res = 0;
for(let i = 0; i < n; ++i) {
const root = uf.find(i);
count.set(root, (count.get(root) || 0) + 1);
res = Math.max(res, count.get(root));
}
return res;
};
You are given an array of positive integers called nums. Two numbers are considered to be connected if they share a common factor greater than 1. A connected component is a group of numbers where every number is directly or indirectly connected to every other number in the group via these common factors.
Your task is to find the size of the largest such connected component in the array. Each number can only belong to one component, and you must not reuse elements between components.
Constraints:
nums are positive integers.At first glance, the problem seems to ask for the largest group of numbers that are all connected by sharing common factors. If you tried a brute-force approach, you might consider checking every pair of numbers for a common factor, but this would be far too slow for large arrays.
A more efficient way is to notice that the connection between numbers is based on their prime factors. If two numbers share any prime factor, they are connected. So, instead of comparing every pair, we can "group" numbers by their prime factors.
This leads to the idea of using a Union-Find (Disjoint Set Union) data structure. By treating each number as a node, and connecting nodes that share a factor, we can efficiently group numbers into components.
The challenge is to efficiently find and link numbers by their factors, and then determine the largest group formed.
nums, compute all of its prime factors. This can be done efficiently up to 105 using trial division.
Sample Input: nums = [4, 6, 15, 35]
- 4 and 6 share factor 2 → connect(0,1)
- 6 and 15 share factor 3 → connect(1,2)
- 15 and 35 share factor 5 → connect(2,3)
Tracing the unions:
nums and M is the largest number, since checking every pair for a common factor is slow.The key insight is that numbers are connected through shared prime factors, not just direct pairwise comparison. By using Union-Find to group numbers by their factors, and mapping each factor to an index, we efficiently find the largest connected component. This approach avoids brute-force inefficiency and leverages mathematical properties for optimal performance.
The elegance comes from representing the problem as a graph of connections via factors, and using classic data structures to solve it efficiently.