Largest Component Size by Common Factor
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array of unique positive integers nums. Consider the following graph:
- There are
nums.lengthnodes, labelednums[0]tonums[nums.length - 1], - There is an undirected edge between
nums[i]andnums[j]ifnums[i]andnums[j]share a common factor greater than1.
Return the size of the largest connected component in the graph.
Examples
Example 1
Input: nums = [4,6,15,35]
Output: 4
Example 2
Input: nums = [20,50,9,63]
Output: 2
Example 3
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
Constraints
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^5- All the values of
numsare unique.
Solution
Method 1 – Union-Find with Factor Mapping
Intuition
If two numbers share a common factor greater than 1, they should be in the same component. We can use union-find to group numbers by their factors. For each number, union it with all its factors greater than 1. The largest component is the one with the most numbers.
Approach
- For each number, find all its factors greater than 1.
- Use union-find to union the number with each of its factors.
- After processing all numbers, count the size of each component by grouping numbers by their root parent.
- Return the size of the largest component.
Code
C++
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
int n = *max_element(nums.begin(), nums.end());
vector<int> par(n+1);
iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) { return par[x] == x ? x : par[x] = find(par[x]); };
for (int x : nums) {
for (int f = 2; f * f <= x; ++f) {
if (x % f == 0) {
par[find(x)] = find(f);
par[find(x)] = find(x/f);
}
}
}
unordered_map<int, int> cnt;
int ans = 0;
for (int x : nums) ans = max(ans, ++cnt[find(x)]);
return ans;
}
};
Go
func largestComponentSize(nums []int) int {
n := 0
for _, x := range nums { if x > n { n = x } }
par := make([]int, n+1)
for i := range par { par[i] = i }
var find func(int) int
find = func(x int) int { if par[x] != x { par[x] = find(par[x]) }; return par[x] }
for _, x := range nums {
for f := 2; f*f <= x; f++ {
if x%f == 0 {
par[find(x)] = find(f)
par[find(x)] = find(x/f)
}
}
}
cnt := map[int]int{}
ans := 0
for _, x := range nums {
fx := find(x)
cnt[fx]++
if cnt[fx] > ans { ans = cnt[fx] }
}
return ans
}
Java
class Solution {
public int largestComponentSize(int[] nums) {
int n = Arrays.stream(nums).max().getAsInt();
int[] par = new int[n+1];
for (int i = 0; i <= n; ++i) par[i] = i;
for (int x : nums) {
for (int f = 2; f * f <= x; ++f) {
if (x % f == 0) {
union(par, x, f);
union(par, x, x/f);
}
}
}
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0;
for (int x : nums) {
int fx = find(par, x);
cnt.put(fx, cnt.getOrDefault(fx, 0) + 1);
ans = Math.max(ans, cnt.get(fx));
}
return ans;
}
private int find(int[] par, int x) {
if (par[x] != x) par[x] = find(par, par[x]);
return par[x];
}
private void union(int[] par, int x, int y) {
par[find(par, x)] = find(par, y);
}
}
Kotlin
class Solution {
fun largestComponentSize(nums: IntArray): Int {
val n = nums.maxOrNull()!!
val par = IntArray(n+1) { it }
fun find(x: Int): Int = if (par[x] == x) x else { par[x] = find(par[x]); par[x] }
for (x in nums) {
var f = 2
while (f * f <= x) {
if (x % f == 0) {
par[find(x)] = find(f)
par[find(x)] = find(x/f)
}
f++
}
}
val cnt = mutableMapOf<Int, Int>()
var ans = 0
for (x in nums) {
val fx = find(x)
cnt[fx] = cnt.getOrDefault(fx, 0) + 1
ans = maxOf(ans, cnt[fx]!!)
}
return ans
}
}
Python
class Solution:
def largestComponentSize(self, nums: list[int]) -> int:
n = max(nums)
par = list(range(n+1))
def find(x: int) -> int:
if par[x] != x:
par[x] = find(par[x])
return par[x]
for x in nums:
for f in range(2, int(x**0.5)+1):
if x % f == 0:
par[find(x)] = find(f)
par[find(x)] = find(x//f)
cnt = {}
ans = 0
for x in nums:
fx = find(x)
cnt[fx] = cnt.get(fx, 0) + 1
ans = max(ans, cnt[fx])
return ans
Rust
impl Solution {
pub fn largest_component_size(nums: Vec<i32>) -> i32 {
let n = *nums.iter().max().unwrap() as usize;
let mut par: Vec<usize> = (0..=n).collect();
fn find(par: &mut Vec<usize>, x: usize) -> usize {
if par[x] != x { par[x] = find(par, par[x]); }
par[x]
}
for &x in &nums {
let mut f = 2;
while f * f <= x {
if x % f == 0 {
let fx = find(&mut par, x as usize);
let ff = find(&mut par, f as usize);
par[fx] = ff;
let fx = find(&mut par, x as usize);
let ff = find(&mut par, (x/f) as usize);
par[fx] = ff;
}
f += 1;
}
}
let mut cnt = std::collections::HashMap::new();
let mut ans = 0;
for &x in &nums {
let fx = find(&mut par, x as usize);
let c = cnt.entry(fx).or_insert(0);
*c += 1;
if *c > ans { ans = *c; }
}
ans
}
}
TypeScript
class Solution {
largestComponentSize(nums: number[]): number {
const n = Math.max(...nums)
const par = Array.from({length: n+1}, (_, i) => i)
const find = (x: number): number => par[x] === x ? x : (par[x] = find(par[x]))
for (const x of nums) {
for (let f = 2; f * f <= x; ++f) {
if (x % f === 0) {
par[find(x)] = find(f)
par[find(x)] = find(Math.floor(x/f))
}
}
}
const cnt = new Map<number, number>()
let ans = 0
for (const x of nums) {
const fx = find(x)
cnt.set(fx, (cnt.get(fx) ?? 0) + 1)
ans = Math.max(ans, cnt.get(fx)!)
}
return ans
}
}
Complexity
- ⏰ Time complexity:
O(n * sqrt(M)), where n is the length of nums and M is the maximum value in nums. For each number, we check all its factors up to sqrt(M). - 🧺 Space complexity:
O(M), for the union-find parent array and counting map.