#2709

Hard

LeetCode Problem Workspace

Greatest Common Divisor Traversal

Determine if every index in an array can be reached from any other using traversals based on greatest common divisors.

Problem Statement

You are given a 0-indexed integer array nums. You can traverse between indices i and j, i != j, if and only if gcd(nums[i], nums[j]) > 1. Determine if every index can reach every other index through a series of such traversals.

Return true if for every pair of indices i and j where i < j, there exists a sequence of traversals from i to j. Otherwise, return false. Arrays may have up to 10^5 elements with values up to 10^5, emphasizing careful factor mapping and connectivity checks.

Examples

Example 1

Input: nums = [2,3,6]

Output: true

In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2). To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1. To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.

Example 2

Input: nums = [3,9,5]

Output: false

No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.

Example 3

Input: nums = [4,3,12,8]

Output: true

There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Prime Factor Mapping

Factor each number in nums into its prime components. Maintain a map from each prime to the list of indices containing it. This allows efficient connection identification for union operations.

Union-Find Connectivity

Initialize a union-find structure for all indices. For each prime factor, union all indices sharing that factor. After processing all primes, check if all indices are connected, indicating full traversal is possible.

Optimization and Edge Cases

Use a sieve up to MAX_VAL to speed up factorization. Handle numbers equal to 1 separately since they cannot connect to any other index. Ensure union-find uses path compression to maintain time complexity O(n*log(MAX_VAL)).

Complexity Analysis

Metric	Value
Time	O(n*log(MAX_VAL))
Space	O(n)

Time complexity is O(n*log(MAX_VAL)) due to factoring each element and performing union operations. Space complexity is O(n) for storing union-find parent arrays and factor-index mappings.

What Interviewers Usually Probe

Looking for correct factorization strategy and mapping.
Expecting union-find implementation with path compression.
Checking understanding of GCD-based connectivity and edge cases like 1 or primes.

Common Pitfalls or Variants

Common pitfalls

Failing to connect all indices sharing the same prime factor.
Ignoring numbers equal to 1 that break connectivity.
Inefficient factorization causing TLE on large arrays.

Follow-up variants

Allow traversal if gcd >= k instead of >1, changing connectivity conditions.
Array contains repeated numbers, testing union-find handling of duplicates.
Input with maximum values, emphasizing sieve and factorization optimizations.

FAQ

What is the main pattern in Greatest Common Divisor Traversal?

The pattern combines array manipulation with number theory using GCD connections and union-find for connectivity.

How do I handle numbers equal to 1 in this problem?

Numbers equal to 1 cannot connect to any other index since gcd(1, x) is 1, so they may prevent full traversal.

Can repeated numbers affect the solution?

Yes, repeated numbers should be treated normally but can make multiple indices share the same factor, aiding union operations.

What is the time complexity of the optimal approach?

Optimal factorization with union-find gives O(n*log(MAX_VAL)) time and O(n) space, suitable for nums.length up to 10^5.

Is union-find necessary for Greatest Common Divisor Traversal?

Yes, union-find efficiently checks connectivity across indices sharing prime factors, ensuring correct traversal evaluation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


mx = 100010
p = defaultdict(list)
for x in range(1, mx + 1):
    v = x
    i = 2
    while i <= v // i:
        if v % i == 0:
            p[x].append(i)
            while v % i == 0:
                v //= i
        i += 1
    if v > 1:
        p[x].append(v)


class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        m = max(nums)
        uf = UnionFind(n + m + 1)
        for i, x in enumerate(nums):
            for j in p[x]:
                uf.union(i, j + n)
        return len(set(uf.find(i) for i in range(n))) == 1

Continue Practicing

#3378 count connected components in lcm graph #1998 gcd sort of an array #2748 number of beautiful pairs