Algorithm
Problem Name: 952. Largest Component Size by Common Factor
Problem Link: https://leetcode.com/problems/largest-component-size-by-common-factor/
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.
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 * 1041 <= nums[i] <= 105- All the values of
numsare unique.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const largestComponentSize = function (nums) {
const { sqrt } = Math
const n = nums.length
const uf = new UF(n)
const primes = {}
for (let i = 0; i < n; i++) {
const num = nums[i]
const prSet = primesSet(num)
for (const e of prSet) {
if (primes[e] == null) primes[e] = []
primes[e].push(i)
}
}
const vals = Object.values(primes)
for(const idxArr of vals) {
const len = idxArr.length
for(let i = 0; i < len - 1; i++) {
uf.union(idxArr[i], idxArr[i + 1])
}
}
let res = 0
const hash = {}
for(let i = 0; i < n; i++) {
const root = uf.find(i)
if(hash[root] == null) hash[root] = 0
hash[root]++
}
return Math.max(...Object.values(hash))
function primesSet(n) {
const limit = ~~(sqrt(n) + 1)
for (let i = 2; i < limit; i++) {
if (n % i === 0) {
const res = primesSet(n / i)
res.add(i)
return res
}
}
return new Set([n])
}
}
class UF {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i> => i)
}
find(x) {
if (this.root[x] !== x) {
this.root[x] = this.find(this.root[x])
}
return this.root[x]
}
union(x, y) {
const xr = this.find(x)
const yr = this.find(y)
this.root[yr] = xr
}
}
Input
nums = [4,6,15,35]
Output
4
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestComponentSize(self, A):
def find(i):
return i if i == parent[i] else find(parent[i])
def prime_factors(n):
res = set()
while n % 2 == 0:
res.add(2)
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i== 0:
res.add(i)
n //= i
if n > 2:
res.add(n)
return res
parent, dic = list(range(len(A))), {}
for i, n in enumerate(A):
for p in prime_factors(n):
if p in dic:
parent[find(i)] = find(dic[p])
dic[p] = i
for i, x in enumerate(parent):
parent[i] = find(x)
return max(collections.Counter(parent).values())
Input
nums = [4,6,15,35]
Output
4
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0952_LargestComponentSizeByCommonFactor
{
public int LargestComponentSize(int[] A)
{
int maxValue = A.Max();
var uf = new UnionFind(maxValue + 1);
var numFactorMap = new Dictionary < int, int>();
foreach (int num in A)
{
var primeFactors = PrimeDecompose(num);
numFactorMap[num] = primeFactors[0];
for (int i = 0; i < primeFactors.Count - 1; ++i)
uf.Union(primeFactors[i], primeFactors[i + 1]);
}
// count the size of group one by one
int maxGroupSize = 0;
var groupCount = new Dictionary < int, int>();
foreach (int num in A)
{
var groupId = uf.Find(numFactorMap[num]);
groupCount.TryGetValue(groupId, out int count);
groupCount[groupId] = count + 1;
maxGroupSize = Math.Max(maxGroupSize, count + 1);
}
return maxGroupSize;
}
private IList < int> PrimeDecompose(int num)
{
var primeFactors = new List<int>();
int factor = 2;
while (num >= factor * factor)
{
if (num % factor == 0)
{
primeFactors.Add(factor);
num /= factor;
}
else
factor += 1;
}
primeFactors.Add(num);
return primeFactors.Distinct().ToList();
}
public class UnionFind
{
private int[] parents;
private int[] ranks;
public UnionFind(int count)
{
parents = new int[count];
ranks = new int[count];
for (int i = 0; i < count; i++)
parents[i] = i;
}
public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);
return parents[index];
}
public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);
if (pIndex1 == pIndex2) return;
if (ranks[pIndex1] >= ranks[pIndex2])
{
parents[pIndex2] = pIndex1;
ranks[pIndex2]++;
}
else
{
parents[pIndex1] = pIndex2;
ranks[pIndex1]++;
}
}
}
}
}
Input
nums = [20,50,9,63]
Output
2