Largest Component Size by Common Factor

Hard
949.

Largest Component Size by Common Factor

Largest Component Size by Common Factor is a hard coding problem on arrays, math and union find, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var largestComponentSize = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Component Size by Common Factor — Problem & Solution

Largest Component Size by Common Factor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Largest Component Size by Common Factor is a hard coding problem on arrays, math and union find, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Largest Component Size by Common Factor

  1. Hint 1

    Comparing every pair is O(n²) gcd calls — far too slow.

  2. Hint 2

    Two numbers are connected exactly when they share a prime factor.

  3. Hint 3

    So union each number with each of its prime factors, and let the primes act as the glue.

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

  1. Size the union-find to hold both the numbers and every prime up to the maximum.
  2. Factorise each number by trial division up to its square root, unioning it with each distinct prime.
  3. If a factor larger than the square root remains, it is prime; union with it too.
  4. 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

Java

private static int[] lcParent;

private static int lcFind(int x) {
    while (lcParent[x] != x) {
        lcParent[x] = lcParent[lcParent[x]];
        x = lcParent[x];
    }
    return x;
}

private static void lcUni(int a, int b) {
    int ra = lcFind(a), rb = lcFind(b);
    if (ra != rb) lcParent[rb] = ra;
}

public static int largestComponentSize(int[] nums) {
    int mx = 0;
    for (int v : nums) mx = Math.max(mx, v);
    lcParent = new int[mx + 1];
    for (int i = 0; i <= mx; i++) lcParent[i] = i;
    for (int v : nums) {
        int x = v;
        for (int p = 2; (long) p * p <= x; p++) {
            if (x % p != 0) continue;
            lcUni(v, p);
            while (x % p == 0) x /= p;
        }
        if (x > 1) lcUni(v, x);
    }
    Map<Integer, Integer> count = new HashMap<>();
    int best = 0;
    for (int v : nums) {
        int r = lcFind(v);
        int c = count.merge(r, 1, Integer::sum);
        best = Math.max(best, c);
    }
    return best;
}

C++

int largestComponentSize(vector<int>& nums) {
    int mx = 0;
    for (int v : nums) mx = max(mx, v);
    vector<int> parent(mx + 1);
    for (int i = 0; i <= mx; i++) parent[i] = i;
    function<int(int)> find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    auto uni = [&](int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[rb] = ra;
    };
    for (int v : nums) {
        int x = v;
        for (int p = 2; (long long) p * p <= x; p++) {
            if (x % p != 0) continue;
            uni(v, p);
            while (x % p == 0) x /= p;
        }
        if (x > 1) uni(v, x);
    }
    unordered_map<int, int> count;
    int best = 0;
    for (int v : nums) {
        int c = ++count[find(v)];
        best = max(best, c);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Union-Find (Disjoint Set Union)