You are given an integer array of unique positive integers nums. Consider the following graph:
nums.length nodes, labeled nums[0] to nums[nums.length - 1],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 * 1041 <= nums[i] <= 105nums are unique.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:
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:
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_sizeThe 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:
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| Case | How to Handle |
|---|---|
| Empty input array | Return 0, as there are no components. |
| Array with a single element | Return 1, as a single element is a component of size 1. |
| Array with all elements equal to 1 | 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 | 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]) | 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) | 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 | 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 | The Union-Find structure correctly merges components based on shared factors, even with duplicates. |