Largest Group by Shared Factor
Problem
You are given a list of distinct positive integers. Two numbers are linked when they share a common factor greater than 1, and links chain, so numbers that are linked through others belong to the same group. Return the size of the largest group.
Examples
Input: nums = [4, 6, 15, 35]
Output: 4
Why: 4 and 6 share 2, 6 and 15 share 3, 15 and 35 share 5, so all four form one groupInput: nums = [20, 50, 9, 63]
Output: 2
Why: 20 and 50 share 2 and 5, 9 and 63 share 3, and nothing links the two pairsInput: nums = [1, 7]
Output: 1
Why: edge case, 1 has no factor greater than 1, so every group has a single numberHints
0 / 3
Comparing every pair with a gcd check is quadratic, which is too slow for a long list. Two numbers are linked exactly when some prime divides both. Can the primes do the linking?
Treat each prime as a meeting point. A number joins the group of every prime that divides it, so two numbers sharing a prime automatically land in the same group.
Factor each number by trial division up to its square root and union the number with each of its prime factors in a disjoint set. Then find the root of every number and return the largest count of numbers sharing a root. Only numbers are counted, not primes.
Solution
Linking numbers directly needs a check for every pair, but a shared factor greater than 1 always means a shared prime, so each number only has to be unioned with its own prime factors and the primes do the rest. The disjoint set holds two kinds of nodes, numbers and primes, and union by size attaches the smaller tree under the larger one so the trees stay shallow while path halving flattens them further on every find. Because the tree sizes include the prime nodes, the answer counts only numbers per root at the end. Factoring by trial division takes O(√v) per number, so time is O(n · √V) for largest value V, plus near-constant work per union, and space is O(n) for the numbers and their primes.
from collections import Counter
def largest_group(nums):
parent, size = {}, {}
def find(x):
parent.setdefault(x, x)
size.setdefault(x, 1)
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return
if size[ra] < size[rb]: # union by size: small tree under big
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
for v in nums:
find(("num", v))
x, p = v, 2
while p * p <= x: # trial division
if x % p == 0:
union(("num", v), ("prime", p))
while x % p == 0:
x //= p
p += 1
if x > 1: # a prime factor above the square root
union(("num", v), ("prime", x))
groups = Counter(find(("num", v)) for v in nums) # count numbers only
return max(groups.values(), default=0)
print(largest_group([4, 6, 15, 35])) # -> 4
print(largest_group([20, 50, 9, 63])) # -> 2
print(largest_group([1, 7])) # -> 1Stuck on the idea rather than the code? Union by Rank or Size covers it.