Skip to main content

0952 - Largest Component Size by Common Factor (Hard)

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

Problem Statement​

You are given an integer array of unique positive integers nums. Consider the following graph:

  • There are nums.length nodes, labeled nums[0] to nums[nums.length - 1],
  • There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 105
  • All the values of nums are unique.

Approach 1: Factorisation + DSU​

We iterate each number and factorise it. In general, here's the approach.

vector<int> factorize(int x) {
    vector<int> res;
    for (int y = 2; y * y <= x; y++) {
        if (x % y) continue;
        while(x % y == 0) {
            res.push_back(y);
            x /= y;
        }
    }
    if (x > 1) res.push_back(x);
    return res;
}

Once we got the factors, we use DSU to unite each factor and the number.

DSU Template
class dsu {
 public:
  vector<int> root, rank, size;
  int n;
  int cnt;

  dsu(int _n) : n(_n) {
    root.resize(n);
    rank.resize(n);
    size.resize(n);
    for(int i = 0; i < n; i++) {
        root[i] = i;
        rank[i] = 1;
        size[i] = 1;
    }
    cnt = n;
  }

  inline int getCount() { return cnt; }

  inline int get(int x) { return (x == root[x] ? x : (root[x] = get(root[x]))); }

  inline bool unite(int x, int y) {
    x = get(x); y = get(y);
    if (x != y) {
        if (rank[x] > rank[y]) {
            root[y] = x;
        } else if (rank[x] < rank[y]) {
            root[x] = y;
        } else {
            root[y] = x;
            rank[x] += 1;
        }
        cnt--;
        
      return true;
    }
    return false;
  }
};

At the end, we check the size of each group and return the max one.

Written by @wingkwong
int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        dsu d(100005);
        for (auto x : nums) {
            // step 1: factorize each number
            vector<int> f = factorize(x);
            // step 2: unite each number with its factors
            for (int i = 0; i < f.size(); i++) {
                d.unite(x, f[i]);
            }
        }
        // step 3: find out the max group size
        int ans = 0;
        unordered_map<int, int> m;
        for (auto x : nums) {
            ans = max(ans, ++m[d.get(x)]);
        }
        return ans;
    }