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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
    // Time: O(N * sqrt(M))
    // Space: O(N + sqrt(M))
    class UnionFind {
        vector<int> id, size;
    public:
        UnionFind(int N) : id(N), size(N, 1) {
            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;
            size[q] += size[p];
        }
        int getSize(int a) { return size[find(a)]; }
    };
    class Solution {
        vector<int> factors(int n) {
            vector<int> ans;
            for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) ans.push_back(i);
                while (n % i == 0) n /= i;
            }
            if (n > 1) ans.push_back(n);
            return ans;
        }
    public:
        int largestComponentSize(vector<int>& A) {
            int N = A.size(), ans = 0;
            UnionFind uf(N);
            unordered_map<int, int> m;  // primce factor -> a representative (the first) number with this factor
            for (int i = 0; i < N; ++i) {
                for (int &f : factors(A[i])) { 
                    if (m.count(f)) uf.connect(i, m[f]);
                    else m[f] = i;
                }
            }
            for (int i = 0; i < N; ++i) ans = max(ans, uf.getSize(i));
            return ans;
        }
    };
    
  • class Solution:
        def largestComponentSize(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            ma = max(A)
            N = len(A)
            m = list(range(ma + 1))
            for a in A:
                for k in range(2, int(math.sqrt(a)) + 1):
                    if a % k == 0:
                        self.u(m, a, k)
                        self.u(m, a, a // k)
            count = collections.defaultdict(int)
            for a in A:
                count[self.f(m, a)] += 1
            return max(count.values())
            
        def f(self, m, a):
            while m[a] != a:
                m[a] = m[m[a]]
                a = m[a]
            return a
        
        def u(self, m, a, b):
            if m[a] == m[b]: return
            pa = self.f(m, a)
            pb = self.f(m, b)
            m[pa] = pb
    

All Problems

All Solutions