# Greatest Common Divisor Traversal
**Difficulty:** HARD
[External](https://leetcode.com/problems/greatest-common-divisor-traversal)
Canonical: https://scaleengineer.com/dsa/problems/greatest-common-divisor-traversal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
---
## 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, 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 = [2,3,6]
**Output:** true
**Explanation:** 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
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Brute-Force with Pairwise GCD Check
This approach treats the problem as a graph connectivity problem. We can determine if all nodes are connected by checking every pair of numbers. If their Greatest Common Divisor (GCD) is greater than 1, they are connected. We can use a Disjoint Set Union (DSU) data structure to efficiently track the connected components. We iterate through all possible pairs of indices, and if their corresponding numbers share a common factor, we merge their sets. Finally, we check if all indices belong to a single component.
**Time:** O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. We iterate through O(N^2) pairs, and for each pair, the GCD calculation takes O(log(M)) time. · **Space:** O(N), where N is the number of elements in `nums`. This space is used for the DSU data structure.
**Pros:** Simple to conceptualize and implement.; Correctly solves the problem for small inputs.
**Cons:** The time complexity of O(N^2 * log(M)) is too high for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The brute-force approach involves checking every possible pair of numbers in the array. For each pair `(nums[i], nums[j])`, we calculate their GCD. If the GCD is greater than 1, it means we can traverse between index `i` and `j`, so we consider them part of the same connected component.

We use a Disjoint Set Union (DSU) data structure to keep track of these components. Initially, each index is in its own component. When we find a pair `(i, j)` with `gcd(nums[i], nums[j]) > 1`, we merge the components of `i` and `j` using the `union` operation.

After iterating through all `O(N^2)` pairs, we check the number of disjoint sets remaining in our DSU structure. If there is only one set, it means all indices are mutually reachable, and the graph is connected. We return `true`. Otherwise, we return `false`.

```java
class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return true;
        }

        DSU dsu = new DSU(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    dsu.union(i, j);
                }
            }
        }

        return dsu.getComponents() == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    class DSU {
        int[] parent;
        int components;

        public DSU(int n) {
            parent = new int[n];
            components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootJ] = rootI;
                components--;
            }
        }

        public int getComponents() {
            return components;
        }
    }
}
```
### Algorithm
- The problem can be modeled as a graph problem. Each index of the `nums` array is a node in the graph.
- An edge exists between two nodes (indices) `i` and `j` if `gcd(nums[i], nums[j]) > 1`.
- The question is equivalent to checking if this graph is connected.
- A straightforward way to check for connectivity is to build the graph and then perform a graph traversal (like DFS or BFS) to see if all nodes can be reached from a single source.
- A more direct way that avoids building an explicit adjacency list is to use a Disjoint Set Union (DSU) data structure.
- Initialize a DSU structure with `N` sets, one for each index.
- Iterate through every pair of indices `(i, j)`.
- If `gcd(nums[i], nums[j]) > 1`, perform a `union` operation on the sets containing `i` and `j`.
- After checking all pairs, if there's only one disjoint set left, it means the graph is fully connected.

## Efficient Approach using DSU and Prime Factorization
A more efficient approach avoids the O(N^2) pairwise comparisons by focusing on the prime factors of the numbers. The condition `gcd(a, b) > 1` is equivalent to `a` and `b` sharing at least one common prime factor. This means we can form connected components by linking numbers that share prime factors.

We can use a Disjoint Set Union (DSU) data structure to group indices. For each number in the input array, we find its prime factors. Then, for each prime factor, we union the current number's index with the index of the first number we saw that had this prime factor. This way, all numbers sharing a prime factor will end up in the same component.

To make prime factorization fast, we first pre-compute the smallest prime factor for all numbers up to the maximum value in the input array using a sieve.
**Time:** O(M * log(log(M)) + N * α(N) * log(M)), where N is `nums.length`, M is `max(nums)`, and α is the Inverse Ackermann function. The sieve takes O(M log log M). The main loop is O(N). Inside, prime factorization takes O(log M) and DSU operations are nearly constant O(α(N)). This simplifies to being dominated by the sieve and the main loop, making it very fast. · **Space:** O(N + M), where N is the length of `nums` and M is the maximum value. O(N) for the DSU, O(M) for the SPF array, and up to O(π(M)) for the map, where π(M) is the number of primes up to M.
**Pros:** Highly efficient, with a time complexity that passes the given constraints.; Scales well for large inputs where N and M are up to 10^5.
**Cons:** The implementation is more complex, requiring knowledge of number theory concepts like sieves and prime factorization.; It uses more space due to the SPF array and the map, with a complexity of O(N + M).
### Explanation
This optimized solution leverages number theory to avoid the costly pairwise checks. Here's a step-by-step breakdown:

1.  **Edge Cases:** A single-element array is trivially connected. If the array has more than one element and contains a `1`, it's impossible to connect the index of `1` to any other index, since `gcd(1, x) = 1` for all `x`. So, we handle these cases first.

2.  **Sieve for Smallest Prime Factor (SPF):** We find the maximum value `M` in `nums`. Then, we use a sieve (similar to Sieve of Eratosthenes) to create an `spf` array of size `M+1`. `spf[k]` will store the smallest prime factor of `k`. This pre-computation takes `O(M log log M)` time and allows us to find the prime factors of any number `x <= M` in `O(log x)` time.

3.  **DSU and Prime-to-Index Map:** We initialize a DSU structure for `N` indices. We also use a `HashMap<Integer, Integer>` called `primeToIndex` which will map a prime number to the first index `i` we encounter where `nums[i]` is divisible by that prime.

4.  **Union by Prime Factors:** We iterate through `nums`. For each `nums[i]`, we find its unique prime factors. For each prime factor `p`, we check our `primeToIndex` map. If `p` is already in the map, it means another number `nums[j]` (where `j = primeToIndex.get(p)`) shares this prime factor. We then call `dsu.union(i, j)`. If `p` is not in the map, we add it, mapping it to the current index `i`.

5.  **Final Connectivity Check:** After processing all numbers, if all indices have been merged into a single component in the DSU, it means the entire graph is connected. We can check this by seeing if the number of components in the DSU is 1.

```java
import java.util.*;

class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;

        int maxVal = 0;
        for (int num : nums) {
            if (num == 1) return false; // If n > 1 and 1 is present, impossible.
            maxVal = Math.max(maxVal, num);
        }

        int[] spf = new int[maxVal + 1];
        for (int i = 2; i <= maxVal; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i <= maxVal; i++) {
            if (spf[i] == i) { // i is a prime number
                for (int j = i * i; j <= maxVal; j += i) {
                    if (spf[j] == j) { // If spf[j] hasn't been set yet
                        spf[j] = i;
                    }
                }
            }
        }

        DSU dsu = new DSU(n);
        Map<Integer, Integer> primeToIndex = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            while (num > 1) {
                int p = spf[num];
                if (primeToIndex.containsKey(p)) {
                    dsu.union(i, primeToIndex.get(p));
                } else {
                    primeToIndex.put(p, i);
                }
                while (num % p == 0) {
                    num /= p;
                }
            }
        }

        return dsu.getComponents() == 1;
    }

    class DSU {
        int[] parent;
        int[] size;
        int components;

        public DSU(int n) {
            parent = new int[n];
            size = new int[n];
            components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (size[rootI] < size[rootJ]) {
                    int temp = rootI;
                    rootI = rootJ;
                    rootJ = temp;
                }
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
                components--;
            }
        }

        public int getComponents() {
            return components;
        }
    }
}
```
### Algorithm
- The core idea is that two numbers `nums[i]` and `nums[j]` are connected if they share a common prime factor.
- Instead of checking pairs of numbers, we can connect indices based on their prime factors. If `nums[i]` and `nums[j]` both have a prime factor `p`, they are in the same connected component.
- We can use a DSU data structure on the indices of the array.
- The overall algorithm is as follows:
  1. Handle edge cases: If `n=1`, return `true`. If `n > 1` and `1` is present in `nums`, return `false` because `1` cannot be connected to any other number.
  2. Find the maximum value `M` in `nums`.
  3. Pre-compute the Smallest Prime Factor (SPF) for all numbers up to `M` using a sieve. This will allow for efficient prime factorization of each number.
  4. Initialize a DSU for `N` indices and a hash map `primeToIndex` to store the first index encountered for each prime factor.
  5. Iterate through each index `i` from `0` to `N-1`:
     a. Get the unique prime factors of `nums[i]` using the pre-computed SPF array.
     b. For each prime factor `p`:
        i. If `primeToIndex` already contains `p`, it means we've seen this prime before at index `j = primeToIndex.get(p)`. We union the sets of `i` and `j`.
        ii. Otherwise, we map this prime `p` to the current index `i` in `primeToIndex`.
  6. After iterating through all numbers, check if the DSU has only one component. If so, all pairs are traversable, and we return `true`.

# Solutions
### Java

```java
class UnionFind { private int [] p ; private int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } } class Solution { private static final int MX = 100010 ; private static final List < Integer >[] P = new List [ MX ]; static { Arrays . setAll ( P , k -> new ArrayList <>()); for ( int x = 1 ; x < MX ; ++ x ) { int v = x ; int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { P [ x ]. add ( i ); while ( v % i == 0 ) { v /= i ; } } ++ i ; } if ( v > 1 ) { P [ x ]. add ( v ); } } } public boolean canTraverseAllPairs ( int [] nums ) { int m = Arrays . stream ( nums ). max (). getAsInt (); int n = nums . length ; UnionFind uf = new UnionFind ( n + m + 1 ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j : P [ nums [ i ]]) { uf . union ( i , j + n ); } } Set < Integer > s = new HashSet <>(); for ( int i = 0 ; i < n ; ++ i ) { s . add ( uf . find ( i )); } return s . size () == 1 ; } }
```

### CPP

```cpp
int MX = 100010 ; vector < int > P [ 100010 ]; int init = []() { for ( int x = 1 ; x < MX ; ++ x ) { int v = x ; int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { P [ x ]. push_back ( i ); while ( v % i == 0 ) { v /= i ; } } ++ i ; } if ( v > 1 ) { P [ x ]. push_back ( v ); } } return 0 ; }(); class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private: vector < int > p , size ; }; class Solution { public: bool canTraverseAllPairs ( vector < int >& nums ) { int m = * max_element ( nums . begin (), nums . end ()); int n = nums . size (); UnionFind uf ( m + n + 1 ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j : P [ nums [ i ]]) { uf . unite ( i , j + n ); } } unordered_set < int > s ; for ( int i = 0 ; i < n ; ++ i ) { s . insert ( uf . find ( i )); } return s . size () == 1 ; } };
```

### Python

```python
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
```