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)

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

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

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

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

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.