Largest Component Size by Common Factor
Problem
You are given an array of unique positive integers nums. Two numbers are connected if they share a common factor greater than 1. Connectivity is transitive: if a is connected to b and b is connected to c, then a, b and c are all in the same group. Return the size of the largest connected group.
nums = [4, 6, 15, 35]4def largest_component_size(nums):
parent = {}
def find(x):
parent.setdefault(x, x)
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
parent[find(a)] = find(b)
for v in nums:
f, x = 2, v
while f * f <= x:
if x % f == 0:
union(v, f)
while x % f == 0:
x //= f
f += 1
if x > 1:
union(v, x)
from collections import Counter
count = Counter(find(v) for v in nums)
return max(count.values())function largestComponentSize(nums) {
const parent = new Map();
function find(x) {
if (!parent.has(x)) parent.set(x, x);
while (parent.get(x) !== x) {
parent.set(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
function union(a, b) { parent.set(find(a), find(b)); }
for (const v of nums) {
let x = v;
for (let f = 2; f * f <= x; f++) {
if (x % f === 0) {
union(v, f);
while (x % f === 0) x = Math.floor(x / f);
}
}
if (x > 1) union(v, x);
}
const count = new Map();
let best = 0;
for (const v of nums) {
const r = find(v);
const c = (count.get(r) || 0) + 1;
count.set(r, c);
best = Math.max(best, c);
}
return best;
}class Solution {
Map<Integer, Integer> parent = new HashMap<>();
int find(int x) {
parent.putIfAbsent(x, x);
while (parent.get(x) != x) {
parent.put(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
void union(int a, int b) { parent.put(find(a), find(b)); }
public int largestComponentSize(int[] nums) {
for (int v : nums) {
int x = v;
for (int f = 2; (long) f * f <= x; f++) {
if (x % f == 0) {
union(v, f);
while (x % f == 0) x /= f;
}
}
if (x > 1) union(v, x);
}
Map<Integer, Integer> count = new HashMap<>();
int best = 0;
for (int v : nums) {
int r = find(v);
int c = count.merge(r, 1, Integer::sum);
best = Math.max(best, c);
}
return best;
}
}class Solution {
unordered_map<int, int> parent;
int find(int x) {
if (!parent.count(x)) parent[x] = x;
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void unite(int a, int b) { parent[find(a)] = find(b); }
public:
int largestComponentSize(vector<int>& nums) {
for (int v : nums) {
int x = v;
for (int f = 2; (long long) f * f <= x; f++) {
if (x % f == 0) {
unite(v, f);
while (x % f == 0) x /= f;
}
}
if (x > 1) unite(v, x);
}
unordered_map<int, int> count;
int best = 0;
for (int v : nums) best = max(best, ++count[find(v)]);
return best;
}
};Explanation
Two numbers belong together if they share a factor greater than 1, and that grouping is transitive. The smart move is to connect numbers through their prime factors using union-find, rather than comparing every pair of numbers.
The key insight: instead of unioning numbers directly, we union each number with every prime that divides it. Then two numbers sharing a prime end up with the same root automatically — the shared prime acts as the bridge.
For each value v we factorize it by trial division: try divisors f up to √v, and whenever f divides v we union(v, f) and strip out all factors of f. If anything bigger than 1 remains, it's a large prime factor, so we union with that too.
After processing every number, we run find on each value to get its group root and count how many numbers share each root with a counter. The biggest count is the answer.
Example: nums = [4, 6, 15, 35]. 4 and 6 share prime 2, 6 and 15 share 3, 15 and 35 share 5. These overlaps chain all four into one group, so the largest component size is 4.