Formatted question description: https://leetcode.ca/all/952.html

952. Largest Component Size by Common Factor (Hard)

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

Example 2:

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

Example 3:

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

Note:

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

Related Topics:
Math, Union Find

Solution 1. Union Find + Factor

The number of elements is big. Can we reduce the scale? Consider all the primes that are factors of numbers in A.

For each number A[i], we union all the factors of A[i]. In this way, A[i]s are grouped according to factors. The size of the biggest group is the result.

// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/

// Time: O(N * sqrt(W)) where N is length of A, W is max(A[i])
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int N) : id(N) {
        iota(begin(id), end(id), 0);
    }    
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
    }
};
class Solution {
    vector<int> factors(int n) {
        vector<int> ans;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i) continue;
            ans.push_back(i);
            while (n % i == 0) n /= i;
        }
        if (n > 1 || ans.empty()) ans.push_back(n);
        return ans;
    }
public:
    int largestComponentSize(vector<int>& A) {
        vector<vector<int>> F;
        unordered_map<int, int> m;
        int i = 0, ans = 0;
        for (int n : A) {
            auto f = factors(n);
            F.push_back(f);
            for (int x : f) {
                if (!m.count(x)) m[x] = i++;
            }
        }
        UnionFind uf(m.size());
        for (auto &f : F) {
            for (int x : f) uf.connect(m[f[0]], m[x]);
        }
        vector<int> cnt(m.size());
        for (auto &f : F) ans = max(ans, ++cnt[uf.find(m[f[0]])]);
        return ans;
    }
};

Java

class Solution {
    public int largestComponentSize(int[] A) {
        int max = 0;
        for (int num : A)
            max = Math.max(max, num);
        int[] parents = new int[max + 1];
        for (int i = 0; i <= max; i++)
            parents[i] = i;
        for (int num : A) {
            int sqrt = (int) Math.sqrt(num);
            for (int i = 2; i <= sqrt; i++) {
                if (num % i == 0) {
                    union(parents, num, i);
                    union(parents, num, num / i);
                }
            }
        }
        int[] counts = new int[max + 1];
        int maxSize = 0;
        for (int num : A) {
            int ancestor = find(parents, num);
            counts[ancestor]++;
            maxSize = Math.max(maxSize, counts[ancestor]);
        }
        return maxSize;
    }

    public void union(int[] parents, int num1, int num2) {
        int ancestor1 = find(parents, num1);
        int ancestor2 = find(parents, num2);
        if (ancestor1 != ancestor2)
            parents[ancestor1] = ancestor2;
    }

    public int find(int[] parents, int num) {
        while (parents[num] != num) {
            parents[num] = parents[parents[num]];
            num = parents[num];
        }
        return num;
    }
}

All Problems

All Solutions