Count Connected Components in LCM Graph - Practice Coding Problems

Count Connected Components in LCM Graph - Problem

Array Hash Table Math Union Find Number Theory Hard

You are given an array of integers nums of size n and a positive integer threshold. There is a graph consisting of n nodes with the i-th node having a value of nums[i].

Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold.

Return the number of connected components in this graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph. The term lcm(a, b) denotes the least common multiple of a and b.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,6,3,4], threshold = 6

› Output: 2

💡 Note: LCM(2,6) = 6 ≤ 6, so nodes 0,1 connect. LCM(6,3) = 6 ≤ 6, so nodes 1,2 connect. This forms one component {0,1,2}. Node 3 is isolated since LCM(4,x) > 6 for all other values. Total: 2 components.

Example 2 — All Disconnected

$ Input: nums = [3,4,6,8], threshold = 2

› Output: 4

💡 Note: All LCM values exceed threshold 2: LCM(3,4)=12, LCM(3,6)=6, LCM(3,8)=24, etc. No connections exist, so each node forms its own component.

Example 3 — All Connected

$ Input: nums = [1,2,3], threshold = 6

› Output: 1

💡 Note: LCM(1,2)=2≤6, LCM(1,3)=3≤6, LCM(2,3)=6≤6. All nodes are connected in one large component.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁵
1 ≤ threshold ≤ 10¹⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of numbers and threshold value

Build Connections

Connect pairs where LCM ≤ threshold

Count Components

Find separate connected groups

Key Takeaway

🎯 Key Insight: Build a graph where edges connect numbers with LCM ≤ threshold, then count connected components using Union-Find or DFS

Asked in

G Google 12 M Microsoft 8 a Amazon 6

This problem builds a graph where nodes connect if their LCM ≤ threshold, then counts connected components. The key insight is recognizing this as a graph connectivity problem. Union-Find provides the cleanest solution with O(n²) time for checking all pairs and O(n) space for the data structure.

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set)	O(n²)	O(n)	Use Union-Find to efficiently group connected nodes
Brute Force with DFS	O(n²)	O(n²)	Check all pairs for connections, use DFS to count components

Union-Find (Disjoint Set) — Algorithm Steps

Initialize Union-Find with n components
For each pair with LCM ≤ threshold, union them
Count remaining distinct components

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each node starts as its own parent

Union Connected

Merge nodes when LCM ≤ threshold

Count Roots

Count distinct root parents

Code -

solution.c — C

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

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

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->size = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    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->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    return (a * b) / gcd(a, b);
}

int solution(int* nums, int numsSize, int threshold) {
    if (numsSize == 0) return 0;
    
    UnionFind* uf = createUnionFind(numsSize);
    
    // Union nodes with LCM <= threshold
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (lcm((long long)nums[i], (long long)nums[j]) <= threshold) {
                unionSets(uf, i, j);
            }
        }
    }
    
    // Count distinct components
    bool* seen = (bool*)calloc(numsSize, sizeof(bool));
    int components = 0;
    for (int i = 0; i < numsSize; i++) {
        int root = find(uf, i);
        if (!seen[root]) {
            seen[root] = true;
            components++;
        }
    }
    
    // Cleanup
    free(uf->parent);
    free(uf->rank);
    free(uf);
    free(seen);
    
    return components;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        nums[numsSize++] = strtol(ptr, &ptr, 10);
        if (*ptr == ',') ptr++;
    }
    
    int threshold;
    scanf("%d", &threshold);
    
    printf("%d\n", solution(nums, numsSize, threshold));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Still need to check all n×n pairs for LCM connections

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find parent array only needs O(n) space

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 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 (Disjoint Set) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler