We’re preparing your current view and syncing the latest data.
Largest Connected Component Size By Common Factor
gfgYou are given an array of unique positive integers nums. Consider the following graph:
Return the size of the largest connected component in the graph.
A common factor of a set of numbers is a positive integer that divides all numbers in the set.
An integer array nums where each element is a unique positive integer.
An integer representing the size of the largest connected component formed by nodes connected through common factors greater than 1.
1 <= nums.length <= 2 * 10^4 1 <= nums[i] <= 10^5 All the values of nums are unique.
Example 1
Input
[4,6,15,35]
Output
4
Explanation
All numbers are connected: 4 and 6 share factor 2, 6 and 15 share factor 3, 15 and 35 share factor 5.
Example 2
Input
[20,50,9,63]
Output
2
Explanation
20 and 50 are connected through factor 10, and 9 and 63 are connected through factor 3, but these two groups are separate.
Example 3
Input
[2,3,6,7,4,12,21,39]
Output
8
Explanation
All numbers are connected through common factors forming one big connected component.