Largest Component Size by Common Factor - Practice Coding Problems

Largest Component Size by Common Factor - Problem

Array Hash Table Math Union Find Number Theory Hard

You are given an integer array nums of unique positive integers. 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.

Input & Output

Example 1 — All Connected

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

› Output: 4

💡 Note: 4 and 6 share factor 2, 6 and 15 share factor 3, 15 and 35 share factor 5. All numbers form one connected component of size 4.

Example 2 — Multiple Components

$ Input: nums = [20,50,9,63]

› Output: 2

💡 Note: 20 and 50 share factor 2 and 5 (component size 2). 9 and 63 share factor 3 (component size 2). Largest component has size 2.

Example 3 — All Separate

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

› Output: 8

💡 Note: Multiple numbers share common factors: 2-4-6-12, 3-6-12-21-39. All form one large connected component.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁵
All the values of nums are unique.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of unique positive integers [4,6,15,35]

Connect

Numbers connect if they share a common factor > 1

Output

Size of largest connected component: 4

Key Takeaway

🎯 Key Insight: Numbers form a connected graph through shared prime factors - use Union-Find for efficient component detection

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is that numbers are connected through shared prime factors, not direct GCD comparison. The optimal approach uses Union-Find with prime factorization to efficiently group connected components. Time: O(n × √max(nums)), Space: O(n + P) where P is the number of unique prime factors.

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Prime Factorization	O(n × √max(nums))	O(n + P)	Use Union-Find to group numbers by shared prime factors efficiently
Brute Force with DFS	O(n² × log(max(nums)))	O(n²)	Check all pairs for common factors, build graph, then find largest component with DFS

Union-Find with Prime Factorization — Algorithm Steps

Step 1: Find all prime factors for each number
Step 2: Use Union-Find to connect numbers sharing prime factors
Step 3: Count size of each connected component

Visualization

Tap to expand

Step-by-Step Walkthrough

Prime Factors

Find prime factors of each number

Group by Primes

Union numbers sharing prime factors

Count Components

Find largest connected component

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* parent;
    int* size;
    int n;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->size = (int*)malloc(n * sizeof(int));
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->size[i] = 1;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    if (px == py) return;
    
    if (uf->size[px] < uf->size[py]) {
        int temp = px;
        px = py;
        py = temp;
    }
    uf->parent[py] = px;
    uf->size[px] += uf->size[py];
}

int getMaxComponentSize(UnionFind* uf) {
    int maxSize = 0;
    for (int i = 0; i < uf->n; i++) {
        int root = find(uf, i);
        if (uf->size[root] > maxSize) {
            maxSize = uf->size[root];
        }
    }
    return maxSize;
}

void getPrimeFactors(int n, int* factors, int* factorCount) {
    *factorCount = 0;
    int d = 2;
    while (d * d <= n) {
        if (n % d == 0) {
            factors[(*factorCount)++] = d;
            while (n % d == 0) {
                n /= d;
            }
        }
        d++;
    }
    if (n > 1) {
        factors[(*factorCount)++] = n;
    }
}

int solution(int* nums, int n) {
    if (n == 1) return 1;
    
    UnionFind* uf = createUnionFind(n);
    
    // Simple approach: group by prime factors
    int maxFactor = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > maxFactor) maxFactor = nums[i];
    }
    
    int* primeToFirst = (int*)malloc((maxFactor + 1) * sizeof(int));
    for (int i = 0; i <= maxFactor; i++) {
        primeToFirst[i] = -1;
    }
    
    for (int i = 0; i < n; i++) {
        int factors[100];
        int factorCount;
        getPrimeFactors(nums[i], factors, &factorCount);
        
        for (int j = 0; j < factorCount; j++) {
            int factor = factors[j];
            if (primeToFirst[factor] == -1) {
                primeToFirst[factor] = i;
            } else {
                unionSets(uf, primeToFirst[factor], i);
            }
        }
    }
    
    int result = getMaxComponentSize(uf);
    
    free(uf->parent);
    free(uf->size);
    free(uf);
    free(primeToFirst);
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9') {
            nums[n++] = strtol(ptr, &ptr, 10);
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × √max(nums))

For each number, find prime factors up to √max, Union-Find operations are nearly O(1)

✓ Linear Growth

Space Complexity

O(n + P)

Union-Find structure O(n) plus hash map for prime factors O(P)

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find with Prime Factorization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler