Greatest Common Divisor Traversal

Difficulty: Hard Source: NeetCode

Problem

You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.

Your task is to determine if for every pair of indices i and j in nums, there exists a sequence of traversals that can take us from i to j.

Return True if it is possible to traverse between all such pairs of indices, or False otherwise.

Example 1: Input: nums = [2,3,6] Output: True

Example 2: Input: nums = [3,9,5] Output: False

Example 3: Input: nums = [4,3,12,8] Output: True

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Union-Find — tracking connected components
• Prime Factorization — decomposing numbers into their prime factors
• Graph Connectivity — checking if all nodes belong to one component

1. Brute Force (Pairwise GCD Check)

Intuition

For every pair of indices (i, j), compute their GCD. If it’s greater than 1, add an edge between them. Then check if the resulting graph is fully connected using BFS or Union-Find. This is O(n²) pairs times the GCD computation — too slow for n = 10^5 but fine conceptually.

Algorithm

1. For each pair (i, j), compute gcd(nums[i], nums[j]).
2. If GCD > 1, union i and j.
3. After all pairs, check if all indices share the same root.

Solution

from math import gcd

def canTraverseAllPairs_brute(nums):
    n = len(nums)
    if n == 1:
        return True

    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[py] = px

    for i in range(n):
        for j in range(i + 1, n):
            if gcd(nums[i], nums[j]) > 1:
                union(i, j)

    root = find(0)
    return all(find(i) == root for i in range(1, n))


print(canTraverseAllPairs_brute([2, 3, 6]))    # True
print(canTraverseAllPairs_brute([3, 9, 5]))    # False
print(canTraverseAllPairs_brute([4, 3, 12, 8]))  # True
print(canTraverseAllPairs_brute([1]))            # True

Complexity

• Time: O(n² * log(max_val)) — n² pairs × GCD computation
• Space: O(n) — Union-Find

2. Union-Find via Prime Factorization

Intuition

Two numbers share a GCD > 1 if and only if they share at least one prime factor. So instead of checking pairs directly, we can union each number with all its prime factors, and prime factors with the numbers that share them.

Think of it like a bipartite graph: numbers on one side, primes on the other. If two numbers share a prime, they’re connected through that prime. Union-Find handles this elegantly — we union each number with each of its prime factors.

After processing all numbers, check if all indices (numbers) share the same connected component.

Algorithm

1. Initialize Union-Find over indices 0..n-1 plus prime numbers up to max(nums).
2. For each nums[i], factorize it.
3. For each prime factor p of nums[i], union index i with a “node” representing prime p.
4. After all numbers are processed, check if all indices have the same root.
5. Special case: if any number is 1, it can’t connect to anything (GCD with anything is 1).

Solution

def canTraverseAllPairs(nums):
    n = len(nums)
    if n == 1:
        return True

    # If any number is 1, it can't form a GCD > 1 edge
    # Unless n == 1 (handled above)
    if 1 in nums:
        return False

    MAX_VAL = max(nums) + 1
    # Union-Find over indices 0..n-1 AND prime "virtual nodes" n..n+MAX_VAL
    parent = list(range(n + MAX_VAL))
    rank = [0] * (n + MAX_VAL)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1

    def prime_factors(num):
        factors = []
        d = 2
        while d * d <= num:
            if num % d == 0:
                factors.append(d)
                while num % d == 0:
                    num //= d
            d += 1
        if num > 1:
            factors.append(num)
        return factors

    for i, num in enumerate(nums):
        for p in prime_factors(num):
            # Union index i with the "virtual node" for prime p
            union(i, n + p)

    # Check if all indices share the same root
    root = find(0)
    return all(find(i) == root for i in range(1, n))


print(canTraverseAllPairs([2, 3, 6]))      # True  (2 and 6 share 2; 3 and 6 share 3)
print(canTraverseAllPairs([3, 9, 5]))      # False (5 shares nothing with 3 or 9)
print(canTraverseAllPairs([4, 3, 12, 8]))  # True
print(canTraverseAllPairs([1, 2, 3]))      # False (1 can't connect to anything)
print(canTraverseAllPairs([2]))            # True  (single element)

Complexity

• Time: O(n * sqrt(max_val) * α(n)) — factorize each number + Union-Find operations
• Space: O(n + max_val) — Union-Find with virtual prime nodes

Common Pitfalls

Forgetting that 1 connects to nothing. The number 1 has no prime factors, so it can never form a GCD > 1 edge with any other number. If nums contains 1 and has length > 1, the answer is always False.

Only checking index connectivity without prime virtual nodes. The naive union of pairs is O(n²). The prime factor trick reduces it dramatically by routing connectivity through shared primes.

Off-by-one in virtual node indexing. If index i corresponds to nums[i] (indices 0..n-1), then the virtual node for prime p should be at position n + p. Make sure your Union-Find is large enough: size n + max_val.