Deloitte | COGNIZANT | IBM | CAPGEMINI
def getClusterSizes(signature):
n = len(signature)
dsu = DSU(n)
prime_to_zone = {}
for i, sig in enumerate(signature):
temp = sig
d = 2
while d * d <= temp:
if temp % d == 0:
if d in prime_to_zone:
dsu.union(i, prime_to_zone[d])
else:
prime_to_zone[d] = i
while temp % d == 0:
temp //= d
d += 1
if temp > 1:
if temp in prime_to_zone:
dsu.union(i, prime_to_zone[temp])
else:
prime_to_zone[temp] = i
root_to_size = {}
for i in range(n):
root = dsu.find(i)
root_to_size[root] = root_to_size.get(root, 0) + 1
return [root_to_size[dsu.find(i)] for i in range(n)]
getClusterSizes✅
1.2K ·