Tap here to switch tabs
Problem
Submissions

Problem: Count Connected Components in LCM Graph

Count Connected Components in LCM Graph gives an array of unique positive integers and a threshold. Connect two values when their least common multiple is within threshold, then return the component count.

Statement

You are given an array of unique positive integers nums and a positive integer threshold.

Consider an undirected graph where each element of nums represents a node. There is an edge between two distinct nodes nums[i] and nums[j] if and only if lcm(nums[i],nums[j])≤\mathrm{lcm}(\mathtt{nums[i]}, \mathtt{nums[j]}) \le threshold, wherelcm(x,y)\mathrm{lcm}(x, y) denotes the least common multiple of xx and yy.

Return the total number of connected components in this graph.

Constraints:

  • 1≤1 \le nums.length ≤105\le 10^5

  • 1≤1 \le nums[i] ≤109\le 10^9

  • All elements of nums are unique.

  • 1≤1 \le threshold ≤2×105\le 2 \times 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Connected Components in LCM Graph

Count Connected Components in LCM Graph gives an array of unique positive integers and a threshold. Connect two values when their least common multiple is within threshold, then return the component count.

Statement

You are given an array of unique positive integers nums and a positive integer threshold.

Consider an undirected graph where each element of nums represents a node. There is an edge between two distinct nodes nums[i] and nums[j] if and only if lcm(nums[i],nums[j])≤\mathrm{lcm}(\mathtt{nums[i]}, \mathtt{nums[j]}) \le threshold, wherelcm(x,y)\mathrm{lcm}(x, y) denotes the least common multiple of xx and yy.

Return the total number of connected components in this graph.

Constraints:

  • 1≤1 \le nums.length ≤105\le 10^5

  • 1≤1 \le nums[i] ≤109\le 10^9

  • All elements of nums are unique.

  • 1≤1 \le threshold ≤2×105\le 2 \times 10^5