2709. Greatest Common Divisor Traversal - Explanation

Description

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, where i < j, 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 = [4,3,12]

Output: true

Explanation: There exists three possible pairsof indices. For each pair, the sequence of traversals are:

(0,1) -> [0,2,1]
(0,2) -> [0,2]
(1,2) -> [1,2]

Example 2:

Input: nums = [2,3,7]

Output: false

Constraints:

1 <= nums.length <= 100,000
1 <= nums[i] <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force (DFS)

Intuition

Two indices can be connected if their corresponding values share a common factor greater than 1. We can model this as a graph where each index is a node, and edges connect pairs with GCD > 1. The problem reduces to checking if all nodes belong to a single connected component.

Algorithm

Build an adjacency list where indices i and j are connected if gcd(nums[i], nums[j]) > 1.
Run DFS starting from index 0, marking all reachable nodes.
After DFS, check if all nodes were visited.
Return true if all nodes are in one component, false otherwise.

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        visit = [False] * n
        adj = [[] for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                if gcd(nums[i], nums[j]) > 1:
                    adj[i].append(j)
                    adj[j].append(i)

        def dfs(node):
            visit[node] = True
            for nei in adj[node]:
                if not visit[nei]:
                    dfs(nei)

        dfs(0)
        for node in visit:
            if not node:
                return False
        return True

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(n ^ 2)$

2. Disjoint Set Union

Intuition

Instead of building explicit edges between indices, we can connect indices through their prime factors. Two numbers sharing a prime factor should be in the same component. Using Union-Find, we union each index with the first occurrence of each of its prime factors. This avoids O(n^2) pairwise comparisons.

Algorithm

Initialize a Union-Find structure with n elements.
Maintain a map from prime factors to the first index containing that factor.
For each number, factorize it by trial division.
For each prime factor found:
- If seen before, union the current index with the stored index.
- Otherwise, store the current index for this factor.
Check if all indices belong to one connected component.

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        self.n -= 1
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

    def isConnected(self):
        return self.n == 1

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        uf = UnionFind(len(nums))

        factor_index = {}  # f -> index of value with factor f
        for i, n in enumerate(nums):
            f = 2
            while f * f <= n:
                if n % f == 0:
                    if f in factor_index:
                        uf.union(i, factor_index[f])
                    else:
                        factor_index[f] = i
                    while n % f == 0:
                        n = n // f
                f += 1
            if n > 1:
                if n in factor_index:
                    uf.union(i, factor_index[n])
                else:
                    factor_index[n] = i

        return uf.isConnected()

Time & Space Complexity

Time complexity: $O(m + n\sqrt {m})$
Space complexity: $O(n \log m)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

3. Sieve of Eratosthenes + DSU

Intuition

We can speed up factorization by precomputing the smallest prime factor (SPF) for each number using the Sieve of Eratosthenes. With SPF, we can factorize any number in O(log m) time. We then use Union-Find to connect each index directly to virtual nodes representing primes.

Algorithm

Handle edge cases: single element returns true; any value of 1 returns false.
Build a sieve array where sieve[x] stores the smallest prime factor of x.
Initialize Union-Find with size n + MAX + 1 (indices + virtual prime nodes).
For each index, factorize its value using the sieve and union the index with N + prime for each prime factor.
Verify all indices share the same root in Union-Find.

class UnionFind:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        N = len(nums)
        if N == 1:
            return True
        if any(num == 1 for num in nums):
            return False

        MAX = max(nums)
        sieve = [0] * (MAX + 1)
        p = 2
        while p * p <= MAX:
            if sieve[p] == 0:
                for composite in range(p * p, MAX + 1, p):
                    sieve[composite] = p
            p += 1

        uf = UnionFind(N + MAX + 1)
        for i in range(N):
            num = nums[i]
            if sieve[num] == 0:  # num is prime
                uf.union(i, N + num)
                continue

            while num > 1:
                prime = sieve[num] if sieve[num] != 0 else num
                uf.union(i, N + prime)
                while num % prime == 0:
                    num //= prime

        root = uf.find(0)
        for i in range(1, N):
            if uf.find(i) != root:
                return False
        return True

Time & Space Complexity

Time complexity: $O(m + n \log m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

4. Sieve of Eratosthenes + DFS

Intuition

Rather than Union-Find, we can build an explicit graph connecting indices to virtual prime nodes and use DFS for connectivity. Each index connects to nodes representing its prime factors, and primes connect back to indices. A single DFS from index 0 should reach all indices if they form one component.

Algorithm

Handle edge cases: single element returns true; any value of 1 returns false.
Build a sieve array for smallest prime factors.
Construct an adjacency list where each index i connects to N + prime for each of its prime factors, and vice versa.
Run DFS from index 0, visiting all reachable nodes.
Return true if all indices (0 to N-1) were visited.

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        N = len(nums)
        if N == 1:
            return True
        if any(num == 1 for num in nums):
            return False

        MAX = max(nums)
        sieve = [0] * (MAX + 1)
        p = 2
        while p * p <= MAX:
            if sieve[p] == 0:
                for composite in range(p * p, MAX + 1, p):
                    sieve[composite] = p
            p += 1

        adj = defaultdict(list)
        for i in range(N):
            num = nums[i]
            if sieve[num] == 0:  # num is prime
                adj[i].append(N + num)
                adj[N + num].append(i)
                continue

            while num > 1:
                prime = sieve[num] if sieve[num] != 0 else num
                adj[i].append(N + prime)
                adj[N + prime].append(i)
                while num % prime == 0:
                    num //= prime

        visited = set()
        def dfs(node):
            visited.add(node)
            for nei in adj[node]:
                if nei not in visited:
                    dfs(nei)

        dfs(0)
        for i in range(N):
            if i not in visited:
                return False
        return True

Time & Space Complexity

Time complexity: $O(m + n \log m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

5. Sieve of Eratosthenes + BFS

Intuition

BFS provides an iterative alternative to DFS for checking graph connectivity. We build the same graph structure connecting indices to prime nodes, then use a queue to explore all reachable nodes starting from index 0.

Algorithm

Handle edge cases: single element returns true; any value of 1 returns false.
Build a sieve array for smallest prime factors.
Construct an adjacency list connecting indices to their prime factor nodes (offset by N).
Initialize a queue with index 0 and a visited set.
Process nodes via BFS, adding unvisited neighbors to the queue.
Return true if all indices (0 to N-1) were visited.

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        N = len(nums)
        if N == 1:
            return True
        if any(num == 1 for num in nums):
            return False

        MAX = max(nums)
        sieve = [0] * (MAX + 1)
        p = 2
        while p * p <= MAX:
            if sieve[p] == 0:
                for composite in range(p * p, MAX + 1, p):
                    sieve[composite] = p
            p += 1

        adj = defaultdict(list)
        for i in range(N):
            num = nums[i]
            if sieve[num] == 0:  # num is prime
                adj[i].append(N + num)
                adj[N + num].append(i)
                continue

            while num > 1:
                prime = sieve[num] if sieve[num] != 0 else num
                adj[i].append(N + prime)
                adj[N + prime].append(i)
                while num % prime == 0:
                    num //= prime

        visited = set()
        queue = deque([0])
        visited.add(0)
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append(nei)

        for i in range(N):
            if i not in visited:
                return False
        return True

Time & Space Complexity

Time complexity: $O(m + n \log m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

Common Pitfalls

Not Handling the Value 1 as a Special Case

The number 1 has no prime factors greater than 1, so it cannot share a common factor with any other number. If the array contains 1 and has more than one element, the answer is always false. Failing to check for this edge case will cause incorrect results or infinite loops during factorization.

Forgetting the Single Element Case

When the array has only one element, all pairs are trivially traversable (there are no pairs to check). This should return true regardless of the value. Missing this base case leads to incorrect behavior, especially if your factorization or union-find logic assumes at least two elements.

Incorrect Prime Factorization

When factorizing numbers, you must completely divide out each prime factor before moving to the next. A common bug is incrementing the factor without fully removing it, causing duplicate unions or missed factors. Use a while loop to divide out each prime completely: while (num % prime == 0) num /= prime.

Off-by-One Errors in Virtual Prime Nodes

When using Union-Find with virtual nodes for primes (offset by N), ensure consistent indexing. Array indices run from 0 to N-1, while prime nodes are at positions N + prime. Mixing up these offsets or forgetting to add N when accessing prime nodes causes incorrect unions and false connectivity results.

Memory Issues with Large Prime Values

When the maximum value in the array is large (up to 10^5 or 10^6), allocating arrays sized by the maximum value can consume significant memory. Ensure your sieve and Union-Find structures are appropriately sized as N + MAX + 1 to accommodate both indices and virtual prime nodes without out-of-bounds errors.