Largest Component Size by Common Factor

Largest Component Size by Common Factor is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

Problem statement

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.

Topics and companies

Topics: Array, Hash Table, Math, Union Find, Number Theory.

Reported in interviews at Google.

How to practise Largest Component Size by Common Factor on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * sqrt(m) * alpha(n)) time and O(n + m) space.

Open Largest Component Size by Common Factor in the code editor, or read the Largest Component Size by Common Factor editorial for a worked solution with its approach and complexity analysis.

Where Largest Component Size by Common Factor sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Union-Find (Disjoint Set Union - DSU) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Largest Component Size by Common Factor

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

• Accounts Merge — Medium, same subpattern
• Graph Valid Tree — Medium, same subpattern
• Most Stones Removed with Same Row or Column — Medium, same subpattern
• Number of Connected Components in an Undirected Graph — Medium, same subpattern
• Number of Islands II — Hard, same subpattern
• Redundant Connection — Medium, same subpattern