How should I practice Connected Components with Divisor Threshold?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi online assessment problems in FastPrep.

Is Connected Components with Divisor Threshold associated with InMobi?

FastPrep tags this as a InMobi online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Connected Components with Divisor Threshold

Learn this problem

● Medium

InMobiFULLTIMEOA

Problem statement

Given integers n and t, consider an undirected graph with nodes labeled 1 through n.

An edge exists between two distinct nodes i and j if and only if gcd(i, j) > t.

Return an array [componentCount, largestComponentSize], where componentCount is the total number of connected components and largestComponentSize is the number of nodes in the largest component.

Function

analyzeDivisorComponents(n: int, t: int) → int[]

Examples

Example 1

n = 6t = 2return = [5,2]

Nodes 3 and 6 are connected because gcd(3, 6) = 3 > 2. Every other node is isolated, so there are 5 components and the largest has size 2.

Example 2

n = 5t = 0return = [1,5]

The greatest common divisor of every pair of positive labels is greater than 0, so the graph is connected.

Example 3

n = 4t = 4return = [4,1]

No pair has a greatest common divisor greater than 4. All four nodes are isolated.

Constraints

1 ≤ n ≤ 200,000
0 ≤ t ≤ n