Largest Component Size by Common Factor — Hard Problem & Solution

You are given an array of distinct positive integers. Build a graph whose nodes are those numbers, joining two of them whenever they share a common factor…

Difficulty: Hard
Topics: Arrays, Math, Union Find, Number Theory
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array of distinct positive integers. Build a graph whose nodes are those numbers, joining two of them whenever they share a common factor greater than 1.

Return the size of the largest connected component.

Example 1

Input: nums = [4,6,15,35]
Output: 4
Explanation: `4-6` share 2, `6-15` share 3, `15-35` share 5 — one chain of four.

Example 2

Input: nums = [20,50,9,63]
Output: 2
Explanation: `{20,50}` share 2 and 5; `{9,63}` share 3.

Example 3

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

Constraints

1 <= nums.length <= 20000
1 <= nums[i] <= 100000
All the values of nums are unique.

How to solve Largest Component Size by Common Factor

Instead of joining numbers to numbers, join each number to its prime factors in a union-find. Two numbers sharing a prime then land in the same set automatically, and a final pass counts the numbers per set.

Approach

Size the union-find to hold both the numbers and every prime up to the maximum.
Factorise each number by trial division up to its square root, unioning it with each distinct prime.
If a factor larger than the square root remains, it is prime; union with it too.
Tally how many input numbers fall in each set and return the largest tally.

Why it works

Using primes as intermediaries replaces up to n² pairwise tests with n · number-of-prime-factors unions — and a number below 100 000 has at most six distinct primes. The final tally must count only the input numbers, never the prime helper nodes, which are scaffolding rather than members of the graph.

Complexity

Time — O(n · √maxValue · α)
Space — O(maxValue)

Pitfalls

Counting the prime nodes as members inflates every component.
After dividing out the small primes, any remainder above 1 is itself a prime factor.
nums[i] == 1 has no prime factors and stays a component of size 1.

Reference solution

Python

from typing import List

def largestComponentSize(nums: List[int]) -> int:
    mx = max(nums)
    parent = list(range(mx + 1))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def uni(a: int, b: int) -> None:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    for v in nums:
        x = v
        p = 2
        while p * p <= x:
            if x % p == 0:
                uni(v, p)
                while x % p == 0:
                    x //= p
            p += 1
        if x > 1:
            uni(v, x)
    count = {}
    best = 0
    for v in nums:
        r = find(v)
        count[r] = count.get(r, 0) + 1
        best = max(best, count[r])
    return best

JavaScript

var largestComponentSize = function(nums) {
    var i, mx = 0;
    for (i = 0; i < nums.length; i++) if (nums[i] > mx) mx = nums[i];
    var parent = [];
    for (i = 0; i <= mx; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    var uni = function(a, b) {
        var ra = find(a), rb = find(b);
        if (ra !== rb) parent[rb] = ra;
    };
    for (i = 0; i < nums.length; i++) {
        var x = nums[i];
        for (var p = 2; p * p <= x; p++) {
            if (x % p !== 0) continue;
            uni(nums[i], p);
            while (x % p === 0) x = Math.floor(x / p);
        }
        if (x > 1) uni(nums[i], x);
    }
    var count = new Map();
    var best = 0;
    for (i = 0; i < nums.length; i++) {
        var r = find(nums[i]);
        var cur = count.get(r);
        var c = (cur === undefined ? 0 : cur) + 1;
        count.set(r, c);
        if (c > best) best = c;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue