values of distinct positive integers and an integer limit.
Two numbers of the array are **linked** if their least common multiple is at most limit. Links chain together: if a is linked to b and b to c, then a, b and c all belong to one group. A number linked to nothing forms a group of its own.
Return the number of groups.
Checking every pair is O(n²) with n up to 10⁵. Note that limit is fairly small.values=[3, 5, 6, 10, 25], limit=10 → 3
LCM(3, 6) = 6 and LCM(5, 10) = 10, so those pairs are linked. LCM(3, 5) = 15 and LCM(6, 10) = 30 exceed 10, and 25 alone already exceeds 10. The groups are {3, 6}, {5, 10}, {25}.
values=[1, 7, 20], limit=15 → 2
1 and 7 are linked (LCM = 7), while 20 exceeds 15 and stays alone.
values=[12], limit=5 → 1
A single number is one group, even when it exceeds limit.
values are distinctvalues=[3, 5, 6, 10, 25], limit=10
3
Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.