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 <= A.length <= 20000
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
}

952 - Largest Component Size by Common Factor

952. Largest Component Size by Common Factor (Hard)

Solution 1. Union Find + Factor

All Problems

All Solutions

Welcome to Subscribe On Youtube

952. Largest Component Size by Common Factor (Hard)

Solution 1. Union Find + Factor

All Problems

All Solutions