Solution


Approach 1: Union-Find

We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundant-connection/solution/ for a tutorial on DSU.

Intuition

Let , and . For each value , there is at most one prime factor dividing . Let's call 's "big prime" this , if it exists.

This means that there are at most unique prime divisors of elements in : the big primes correspond to a maximum of values, and the small primes are all less than , so there's at most of them too.

Algorithm

Factor each into prime factors, and index every occurrence of these primes. (To save time, we can use a sieve. Please see this article's comments for more details.)

Then, use a union-find structure to union together any prime factors that came from the same .

Finally, we can count the size of each component, by inspecting and counting the id of the component each belongs to.

Complexity Analysis

  • Time Complexity: where is the length of A, and .

  • Space Complexity: .


Analysis written by: @awice.