Largest Component Size by Common Factor

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array nums of **distinct** positive integers. Build an undirected graph whose nodes are the values in nums, with an edge between two values whenever they share a common factor greater than 1. Return the number of nodes in the largest connected component of this graph. Comparing every pair with gcd is quadratic and too slow for 2 * 10^4 values; connect numbers through their prime factors instead.

Examples

Input: nums = [4,6,15,35]
Output: 4
4-6 share 2, 6-15 share 3, 15-35 share 5, so all four are connected.
Input: nums = [20,50,9,63]
Output: 2
{20, 50} share 2 and 5; {9, 63} share 3; the groups are not linked.
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
Every value connects through 2, 3, or 7 into one component.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 10^5
  • All values in nums are unique

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems