952. Largest Component Size by Common Factor #

Problem #

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i]and A[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. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

Problem Summary #

Given a non-empty array A consisting of distinct positive integers, consider the following graph:

There are A.length nodes, labeled from A[0] to A[A.length - 1]; There is an edge between A[i] and A[j] only when A[i] and A[j] share a common factor greater than 1. Return the size of the largest connected component in the graph.

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

Solution Approach #

• Given an array, if every two elements in the array have a common divisor, then these two elements can be considered related. All related numbers can be placed in one set. The question asks for the maximum number of elements among the sets formed by related elements in this array.
• After reading this problem, the intuitive approach is to solve it with Union-Find. First, you can try a brute-force solution. Use two nested loops to compare pairs and check whether they have a common divisor; if they do, union() them together. After submission, this gets TLE. In fact, looking at the data size makes it clear it will time out: 1 <= A.length <= 20000. Notice that 1 <= A[i] <= 100000; after taking the square root, it is only 316.66666, so the scale of these numbers is not large. Therefore, find all factors of each number that are less than or equal to its square root. For example, 6 = 2 * 3, 15 = 3 * 5; then union() 6 with 2 and 6 with 3, and union() 15 with 3 and 15 with 5. Finally, traverse all sets, find the set with the most elements, and output the number of elements it contains.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

// Solution 1 Union-Find UnionFind
func largestComponentSize(A []int) int {
	maxElement, uf, countMap, res := 0, template.UnionFind{}, map[int]int{}, 1
	for _, v := range A {
		maxElement = max(maxElement, v)
	}
	uf.Init(maxElement + 1)
	for _, v := range A {
		for k := 2; k*k <= v; k++ {
			if v%k == 0 {
				uf.Union(v, k)
				uf.Union(v, v/k)
			}
		}
	}
	for _, v := range A {
		countMap[uf.Find(v)]++
		res = max(res, countMap[uf.Find(v)])
	}
	return res
}

// Solution 2 UnionFindCount
func largestComponentSize1(A []int) int {
	uf, factorMap := template.UnionFindCount{}, map[int]int{}
	uf.Init(len(A))
	for i, v := range A {
		for k := 2; k*k <= v; k++ {
			if v%k == 0 {
				if _, ok := factorMap[k]; !ok {
					factorMap[k] = i
				} else {
					uf.Union(i, factorMap[k])
				}
				if _, ok := factorMap[v/k]; !ok {
					factorMap[v/k] = i
				} else {
					uf.Union(i, factorMap[v/k])
				}
			}
		}
		if _, ok := factorMap[v]; !ok {
			factorMap[v] = i
		} else {
			uf.Union(i, factorMap[v])
		}
	}
	return uf.MaxUnionCount()
}