⚡Flashcard Drill➔
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

  1. Two numbers are connected when they share a prime factor, so prime factors act as hubs.
  2. Union each number with each of its distinct prime factors.
  3. Then all numbers are connected exactly when their union-find roots are all the same.
  4. 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 nums case: 1 has no prime factors, so it is isolated (unless it is the only element).
  • Handling n == 1 separately: 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems