We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Connected Components in LCM Graph

Number: 3680

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of unique integers and a positive integer threshold, we imagine a graph where each number is a node. An undirected edge exists between two nodes i and j if the least common multiple lcm(nums[i], nums[j]) is ≤ threshold. The task is to determine the number of connected components (i.e. groups of mutually “reachable” nodes) in the graph.

Key Insights

  • If a number is larger than the threshold, then for any other number the lcm is at least that number – so nodes with nums[i] > threshold are isolated.
  • For two numbers a and b that are both ≤ threshold, note that lcm(a, b) = (a * b) / gcd(a, b). In many cases (for example when one number divides the other) the condition can be checked more easily.
  • When a divides b then lcm(a, b)=b so an edge exists provided b ≤ threshold.
  • If neither number divides the other then typically (a * b) is “reduced” by the gcd; in fact, if both numbers are “sufficiently large” then in order for a·b/gcd(a,b) to be ≤ threshold the numbers must be very close (or share a very large common divisor). This suggests that aside from unioning numbers by “divisibility–style” connections (by iterating over multiples) it is only necessary to “double‐loop” over the very small numbers (say at most √(threshold)) and also check candidates that are nearly equal.
  • The union–find (disjoint set union) data structure is ideal for “merging” nodes that are connected by a valid edge and later counting connected components.

Space and Time Complexity

Time Complexity: O(M log M + M · (threshold/divisor)) on the “small” part plus an extra double loop on O(√(threshold)) numbers, where M is the number of numbers ≤ threshold. (In worst‐case M is O(n) but most unions are done by iterating over multiples; the extra loops over very small numbers do not blow up.)
Space Complexity: O(n) for storing the union–find structure and hash maps.

Solution

We proceed in two steps:

  1. Pre–processing and “divisibility unions”: Notice that if a divides b and b ≤ threshold, then automatically lcm(a, b)=b ≤ threshold. Thus, we first “union” nodes by iterating over the input numbers that are ≤ threshold. Using a hash map from value to index, for each number v we iterate over multiples m (i.e. 2v, 3v, …, up to threshold) and if m appears in the input we union v and m.
  2. Catching additional “non‐divisible” unions: It is possible that two numbers a and b (both ≤ threshold) do not have a divisor/dividend relation yet still have lcm(a, b) ≤ threshold (for example, a and b may share a large common factor). One key observation is that if both a and b are “large” (greater than √(threshold)) then a*b is “normally” too big unless they are very close or share a huge gcd. Thus, we separately handle the “small” numbers – those ≤ √(threshold) (and possibly check a few adjacent numbers in sorted order for the remaining ones) – by a double–loop. For each pair from the very small group, we compute lcm and if it is ≤ threshold we union them.
  3. Finally, note that any number > threshold is isolated, so each one forms its own connected component. For the rest, after performing the unions the answer is the number of disjoint sets. The “gotchas” include carefully splitting the input based on value (relative to threshold) and recognizing that while in theory every pair among small nodes might be checked, in practice the cost is controlled by the constraint on threshold (and by only “double–looping” on numbers below √(threshold)).

Data structures used include: • A dictionary (or hash map) that maps a number (which is in the input and ≤ threshold) to its index. • The union–find data structure (with path compression and union–by–rank) to “merge” nodes that are connected. • (Optionally) A sorted array for the small numbers to “sweep through” adjacent nearly–equal values. The overall algorithm is a union–find based solution that “builds” the graph implicitly by enumerating candidate connecting edges based on number theory properties of divisibility and lcm.

Code Solutions

# Python solution with line-by-line comments
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n

    def find(self, x):
        # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # union by rank
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

def lcm(a, b):
    # Calculate least common multiple using gcd
    from math import gcd
    return a * b // gcd(a,b)

def countConnectedComponents(nums, threshold):
    n = len(nums)
    uf = UnionFind(n)
    # Map each number to its index for numbers that can be connected (nums[i] <= threshold)
    value_to_index = {}
    small_indices = []  # stores indices for numbers <= threshold
    isolated_indices = []  # numbers greater than threshold
    
    for i, val in enumerate(nums):
        if val <= threshold:
            value_to_index[val] = i
            small_indices.append(i)
        else:
            isolated_indices.append(i)
    
    # 1. Union by divisibility:
    # For a number v, if a multiple m exists (where m = k*v ≤ threshold), then lcm(v, m)=m so union.
    for v in list(value_to_index.keys()):
        multiplier = 2
        while v * multiplier <= threshold:
            m = v * multiplier
            if m in value_to_index:
                uf.union(value_to_index[v], value_to_index[m])
            multiplier += 1

    # 2. For pairs that are not connected by divisibility, check among the “small” numbers.
    # We further only double–loop over numbers that are very small.
    from math import isqrt
    small_vals = []
    for i in small_indices:
        if nums[i] <= isqrt(threshold):
            small_vals.append(i)
    L = len(small_vals)
    for i in range(L):
        for j in range(i+1, L):
            idx1, idx2 = small_vals[i], small_vals[j]
            # if not already in same component, check the lcm condition
            if uf.find(idx1) != uf.find(idx2):
                if lcm(nums[idx1], nums[idx2]) <= threshold:
                    uf.union(idx1, idx2)
    
    # 3. (Optional) For the remaining small numbers (those > sqrt(threshold)), numbers that are “close”
    # might be connected if they share a large gcd. Sorting these by value and checking neighbors.
    other_small = []
    for i in small_indices:
        if nums[i] > isqrt(threshold):
            other_small.append(i)
    other_small.sort(key=lambda i: nums[i])
    for i in range(1, len(other_small)):
        idx_prev = other_small[i-1]
        idx_cur = other_small[i]
        if uf.find(idx_prev) != uf.find(idx_cur):
            if lcm(nums[idx_prev], nums[idx_cur]) <= threshold:
                uf.union(idx_prev, idx_cur)
    
    # Count connected components: 
    # For small numbers, count unique roots. Plus each isolated (nums > threshold) node is its own component.
    seen = set()
    for i in small_indices:
        seen.add(uf.find(i))
    return len(seen) + len(isolated_indices)

# Example usage:
# nums = [2,4,8,3,9]
# threshold = 5
# print(countConnectedComponents(nums, threshold))  # Output: 4
← Back to All Questions