Taro Logo

Largest Component Size by Common Factor

Hard
Asked by:
Profile picture
55 views
Topics:
GraphsArraysGreedy AlgorithmsDynamic Programming

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

Example 1:

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

Example 2:

Input: nums = [20,50,9,63]
Output: 2

Example 3:

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

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 105
  • All the values of nums are unique.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the bounds on the values within the input array A, and what is the maximum length of A?
  2. Are all elements of A positive integers? Can I assume there will be no negative numbers or zeros?
  3. If there are no common factors between any of the numbers in the array (i.e., all components have size 1), what should I return?
  4. Could you define more precisely what you mean by "component size" in this context? Does it refer to the number of elements sharing a common factor, or something else?
  5. If there are multiple components of the same largest size, can I return any one of them (represented by its size)?

Brute Force Solution

Approach

The brute force approach to finding the largest component size by common factor involves checking all possible combinations of numbers to see which ones share common factors. We essentially explore every possible grouping to find the biggest connected group. It's like trying every single team combination to find the biggest team where everyone has something in common.

Here's how the algorithm would work step-by-step:

  1. Start by considering each number individually. It forms a group of size one.
  2. Then, take the first number and compare it to every other number in the list.
  3. If any two numbers share a common factor greater than one, put them in the same group.
  4. Next, take the second number and compare it to every other number (that isn't already compared). If they share a common factor, put them in the same group as the second number.
  5. Continue doing this for every number in the list, building up groups based on common factors.
  6. At the end, you'll have a bunch of different groups. Some might overlap because of shared common factors across different numbers.
  7. Merge any overlapping groups into a single larger group.
  8. Once all groups are finalized and no longer overlapping, count the size of each group.
  9. The largest of these group sizes is your answer: the size of the largest component with common factors.

Code Implementation

def largest_component_size_by_common_factor_brute_force(numbers):
    number_count = len(numbers)
    groups = []

    for i in range(number_count):
        groups.append({numbers[i]})

    def find_greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def share_common_factor(first_number, second_number):
        return find_greatest_common_divisor(first_number, second_number) > 1

    # Iterate through all possible pairs to group numbers with common factors.
    for first_index in range(number_count):
        for second_index in range(first_index + 1, number_count):
            if share_common_factor(numbers[first_index], numbers[second_index]):
                group_one = None
                group_two = None
                for group in groups:
                    if numbers[first_index] in group:
                        group_one = group
                    if numbers[second_index] in group:
                        group_two = group

                # Merge groups if necessary to consolidate common factor relationships.
                if group_one and group_two and group_one != group_two:
                    group_one.update(group_two)
                    groups.remove(group_two)

    # After grouping, consolidate any remaining overlapping groups.
    final_groups = []
    for group in groups:
        is_merged = False
        for existing_group in final_groups:
            if group.intersection(existing_group):
                existing_group.update(group)
                is_merged = True
                break
        if not is_merged:
            final_groups.append(group)

    # Determine and return the largest group size.
    largest_size = 0
    for group in final_groups:
        largest_size = max(largest_size, len(group))

    return largest_size

Big(O) Analysis

Time Complexity
O(n²) – The algorithm iterates through each of the n numbers in the input array. For each number, it compares it with every other number to find common factors. This nested comparison results in approximately n * (n-1) / 2 comparisons. Therefore, the time complexity is dominated by the quadratic term, resulting in O(n²).
Space Complexity
O(N) – The described algorithm involves creating and merging groups based on common factors. In the worst-case scenario, each number could initially belong to its own unique group, requiring us to store up to N groups, where N is the number of input numbers. As the algorithm progresses and merges these groups, it might need to store temporary lists or sets to represent these groups. Since these data structures scale linearly with the number of input numbers, the space complexity is O(N).

Optimal Solution

Approach

The most efficient way to solve this involves grouping numbers based on their shared building blocks (prime factors). Then, we find the largest group, representing the biggest connected component.

Here's how the algorithm would work step-by-step:

  1. First, find the smallest building blocks (prime factors) of each number in the input.
  2. Next, imagine each number and each of its prime factors as separate people, and use a way to group them together where if two people share a common acquaintance (number or prime factor), they are in the same group.
  3. Once everyone is in their respective groups, simply find the group with the most people in it. That's your answer!

Code Implementation

def largestComponentSize(numbers: list[int]) -> int:
    def findPrimeFactors(number: int) -> list[int]:
        prime_factors = []
        divisor = 2
        while divisor * divisor <= number:
            if number % divisor == 0:
                prime_factors.append(divisor)
                while number % divisor == 0:
                    number //= divisor
            divisor += 1
        if number > 1:
            prime_factors.append(number)
        return prime_factors

    parent = list(range(len(numbers) + len(set(sum((findPrimeFactors(number) for number in numbers), [])))))
    size = [1] * len(parent)

    def find(node: int) -> int:
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    def union(node1: int, node2: int) -> None:
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            if size[root1] < size[root2]:
                root1, root2 = root2, root1
            parent[root2] = root1
            size[root1] += size[root2]

    prime_to_index = {}
    next_available_index = len(numbers)

    # Assign prime factors unique indices
    for i, number in enumerate(numbers):
        prime_factors = findPrimeFactors(number)
        for prime_factor in prime_factors:
            if prime_factor not in prime_to_index:
                prime_to_index[prime_factor] = next_available_index
                next_available_index += 1

            # Connect each number to its prime factors
            union(i, prime_to_index[prime_factor])

    component_size_counts = {}
    maximum_component_size = 0

    # Count the size of each component
    for i in range(len(numbers)):
        root = find(i)
        if root not in component_size_counts:
            component_size_counts[root] = 0
        component_size_counts[root] += 1
        maximum_component_size = max(maximum_component_size, component_size_counts[root])

    # Find and return the largest component size
    return maximum_component_size

Big(O) Analysis

Time Complexity
O(n * sqrt(MAX_VAL) + n * alpha(n)) – Finding prime factors for each number in the input array of size n takes O(sqrt(MAX_VAL)) where MAX_VAL is the maximum value in the input array, since we iterate up to the square root to find factors. Building the groups using a Union-Find data structure with path compression and rank optimization takes nearly linear time, or O(n * alpha(n)) where alpha(n) is the inverse Ackermann function, which grows extremely slowly and can be considered almost constant for practical input sizes. Therefore, the overall time complexity is dominated by finding prime factors and grouping elements together, resulting in O(n * sqrt(MAX_VAL) + n * alpha(n)).
Space Complexity
O(N + P) – The algorithm uses a Union-Find data structure to group numbers and their prime factors. The space complexity of Union-Find is primarily determined by the size of the parent array which represents the groups. This array holds N entries for the numbers and P entries for the prime factors, where N is the number of input numbers and P is the number of distinct prime factors across all numbers. Therefore, the auxiliary space is O(N + P), representing the memory required to store the parent array in the Union-Find data structure.

Edge Cases

Empty input array
How to Handle:
Return 0, as there are no components.
Array with a single element
How to Handle:
Return 1, as a single element is a component of size 1.
Array with all elements equal to 1
How to Handle:
Return the array length, since each element is a separate component of size 1 and no common factors exist other than 1.
Array with large prime numbers
How to Handle:
The union find should still function correctly; ensure that the prime factorization is handled efficiently to avoid performance issues.
Array with consecutive numbers (e.g., [2, 3, 4, 5])
How to Handle:
Ensure the prime factorization considers all possible factors in this range, connecting components correctly.
Array with elements exceeding integer limits during intermediate calculations (prime factorization)
How to Handle:
Use long data type to avoid overflow during calculations in languages where integer overflow is not handled by default.
Large array size with limited memory
How to Handle:
Optimize the memory footprint of the Union-Find data structure, possibly using path compression and union by rank.
Array contains duplicate composite numbers with shared factors
How to Handle:
The Union-Find structure correctly merges components based on shared factors, even with duplicates.