Skip to content

0952. Largest Component Size by Common Factor

Given a non-empty array of unique positive integers A, consider the following graph:

  • There are A.length nodes, labelled A[0] to A[A.length - 1];
  • There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

image

Example 2:

Input: [20,50,9,63]
Output: 2

img

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

img

Note:

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= 100000

Analysis - Union-Find w/o Math

tldr: By using map we can save the space from max(array) to sqrt(max(array)).

This question is basically asking the largest connected component in a forest. In order to do so, we need to find a way to "group" all the nodes whose common divisor (one by one, not among any two) is greater than 1 together to a single tree, and we need a "root" as an id to quantify how many kids does this tree hold. This leads to Union-Find.

step 1 build the graph: * start with all the nodes themselves, they are "self-connected"

step 2 find all the divisor of current node * after we put node value to the tree, we also need to group all the divisor >= 2 with current root node. * this can be done with sqrt(n) times, since any two divisor a * b < n, a has to be less than sqrt(n).

step 3 check the root and do the counting * now we have built our tree, and we can easily find the root node (or id) for each node, we can just count the number of id and find the max.

Code

class Solution {
public:
    unordered_map<int, int> p;

    int find(int a) {
        if (!p.count(a)) return p[a] = a;
        if (p[a] == a) return a;
        return p[a] = find(p[a]);
    }

    int largestComponentSize(vector<int>& A) {
        int n = A.size();
        for (int a : A)
            p[a] = a;
        for (int a : A)
            for (int i = 2; i <= sqrt(a); ++i) {
                if (a % i == 0) {                    
                    p[find(a)] = p[find(i)];
                    p[find(a)] = p[find(a / i)];
                }
            }
        unordered_map<int, int> cnt;
        int res = 1;
        for (int a : A)
            res = max(res, ++cnt[find(a)]);
        return res;
    }
};

Q&A: why

for (int a : A) 
    for (int i = 2; i <= sqrt(a); ++i)
        if (a % i == 0) {
            p[find(a)] = p[find(i)];
            p[find(a)] = p[find(a / i)];
        }

instead of

for (int a : A) 
    for (int i = 2; i <= sqrt(a); ++i) {
        int root = find(a);
        if (a % i == 0) {
            p[root] = p[find(i)];
            p[root] = p[find(a / i)];
        }
    }

Because our root is going to change every time when the p map is updated.

Analysis: Union-Find w/ Prime Sieve

Code

class Solution {
    const static int N = 100001;
    int parent[N];
    int m[N];
    int size[N];

    int root(int val){
        while(val != parent[val]) {
            parent[val] = parent[parent[val]];
            val = parent[val];
        }

        return val;
    }

    int unionize(int x, int y){
        int r1 = root(x);
        int r2 = root(y);

        if(r1 == r2)
            return size[r1];

        parent[r1] = r2;
        size[r2] += size[r1];

        return size[r2];
    }

    // sieve algo
    void findPrime(vector<int> &prime){
        prime.resize(N, 0);
        for (int i = 2; i*i < N; i++)
            if (prime[i] == 0)
                for (int j= i*i; j < N; j += i) 
                    prime[j] = i; 

        for(int i = 2 ; i < N; ++i)
            if(prime[i] == 0)
                prime[i] = i;
    }

    void init(int n){
        for(int i = 0 ; i < n; ++i){
            parent[i] = i;
            size[i] = 1;
            m[i] = -1;
        }
    }

public:
    int largestComponentSize(vector<int>& A) {
        static vector<int> prime;
        init (*max_element(A.begin(), A.end()));
        int res = 0;

        if(prime.empty())
            findPrime(prime);

        for (auto a : A) {

            int cur = a;

            while(a > 1){
                int p = prime[a];

                if(m[p] == -1)
                    m[p] = cur;

                res = max(res , unionize(m[p],cur));

                //remove all prime factors p from a
                while(prime[a] == p)
                    a /= p;      
            }        
        }

        return res;
    }
};
Last update: April 1, 2022