hardGraphsPure DSA~35 min
Largest Cluster Sharing a Common Factor
Each dataset is tagged with an integer key. Two datasets belong to the same cluster if their keys share a common factor greater than 1. Find the size of the largest cluster.
Problem
Given an array nums of unique positive integers, two values are connected if they share a common factor greater than 1. Connectivity is transitive. Return the size of the largest connected component.
Input
An array nums of distinct positive integers.
Output
An integer: the size of the largest connected component.
Constraints
- 1 <= nums.length <= 20000
- 1 <= nums[i] <= 100000
- All values in nums are unique.
Examples
Example 1
Input
nums = [4,6,15,35]
Output
4
4-6 (share 2), 6-15 (share 3), 15-35 (share 5) link all four.
Example 2
Input
nums = [20,50,9,63]
Output
2
20-50 share 5; 9-63 share 3; two clusters of size 2.