Welcome to Subscribe On Youtube

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;
    }
};
  • 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;
        }
    }
    
    ############
    
    class UnionFind {
        int[] p;
    
        UnionFind(int n) {
            p = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
            }
        }
    
        void union(int a, int b) {
            int pa = find(a), pb = find(b);
            if (pa != pb) {
                p[pa] = pb;
            }
        }
    
        int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    }
    
    class Solution {
        public int largestComponentSize(int[] nums) {
            int m = 0;
            for (int v : nums) {
                m = Math.max(m, v);
            }
            UnionFind uf = new UnionFind(m + 1);
            for (int v : nums) {
                int i = 2;
                while (i <= v / i) {
                    if (v % i == 0) {
                        uf.union(v, i);
                        uf.union(v, v / i);
                    }
                    ++i;
                }
            }
            int[] cnt = new int[m + 1];
            int ans = 0;
            for (int v : nums) {
                int t = uf.find(v);
                ++cnt[t];
                ans = Math.max(ans, cnt[t]);
            }
            return ans;
        }
    }
    
  • // 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 UnionFind:
        def __init__(self, n):
            self.p = list(range(n))
    
        def union(self, a, b):
            pa, pb = self.find(a), self.find(b)
            if pa != pb:
                self.p[pa] = pb
    
        def find(self, x):
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
    
    
    class Solution:
        def largestComponentSize(self, nums: List[int]) -> int:
            uf = UnionFind(max(nums) + 1)
            for v in nums:
                i = 2
                while i <= v // i:
                    if v % i == 0:
                        uf.union(v, i)
                        uf.union(v, v // i)
                    i += 1
            return max(Counter(uf.find(v) for v in nums).values())
    
    ############
    
    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
    
  • func largestComponentSize(nums []int) int {
    	m := 0
    	for _, v := range nums {
    		m = max(m, v)
    	}
    	p := make([]int, m+1)
    	for i := range p {
    		p[i] = i
    	}
    	var find func(int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	union := func(a, b int) {
    		pa, pb := find(a), find(b)
    		if pa != pb {
    			p[pa] = pb
    		}
    	}
    	for _, v := range nums {
    		i := 2
    		for i <= v/i {
    			if v%i == 0 {
    				union(v, i)
    				union(v, v/i)
    			}
    			i++
    		}
    	}
    	ans := 0
    	cnt := make([]int, m+1)
    	for _, v := range nums {
    		t := find(v)
    		cnt[t]++
    		ans = max(ans, cnt[t])
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions