NeetCode #655LC-2709HardAdvanced GraphsNC 250
← Back to All Problems#655 · #2709 · Greatest Common Divisor Traversal(最大公约数遍历)
📌 Problem Statement & Constraints
You are given a 0-indexed array
nums. You may traverse from index i to index j if gcd(nums[i], nums[j]) > 1. Return whether there is a path visiting every index. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^5.💡 Core Algorithmic Approaches
- Two numbers are connected when they share a prime factor, so prime factors act as hubs.
- Union each number with each of its distinct prime factors.
- Then all numbers are connected exactly when their union-find roots are all the same.
- A smallest-prime-factor sieve gives the factorisation in O(log x) per number.
💻 Benchmark Python3 Implementation
class Solution:
def canTraverseAllPairs(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return True # a single index is trivially reachable
if 1 in nums:
return False # 1 shares no factor with anything
maxv = max(nums)
# smallest prime factor sieve
spf = list(range(maxv + 1))
for i in range(2, int(maxv ** 0.5) + 1):
if spf[i] == i:
for j in range(i * i, maxv + 1, i):
if spf[j] == j:
spf[j] = i
parent = {}
def find(x: int) -> int:
parent.setdefault(x, x)
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> None:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
for x in nums:
v = x
while v > 1:
p = spf[v]
union(x, p) # link the number to its prime factor
while v % p == 0:
v //= p
roots = {find(x) for x in nums}
return len(roots) == 1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V log log V + n log V) where V is the maximum value: the sieve plus the factorisations.
💾 Space Complexity
O(V) for the sieve and the union-find.
⚠️ Interview Pitfalls & Follow-ups
- Pairwise GCD checks: O(n^2 log V), far too slow.
- Forgetting the
1 in numscase: 1 has no prime factors, so it is isolated (unless it is the only element). - Handling
n == 1separately: a single index is trivially traversable. - Unioning numbers directly instead of via prime hubs: you would still need the pairwise GCD.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.