Greatest Common Divisor Traversal

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,_orfalse otherwise.

Examples

Example 1

1
2
3
4
5


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

1
2
3


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

1
2
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 <= 10^5
1 <= nums[i] <= 10^5

Solution

Method 1 – Union-Find with Prime Factorization

Intuition

Two indices are connected if their numbers share a common prime factor. If all indices are in the same connected component (via shared prime factors), then traversal is possible between any pair. We can use Union-Find (DSU) to group indices by their prime factors.

Approach

For each number in nums, factorize it into its prime factors.
For each prime factor, union the index of the number and the prime factor in DSU.
After processing all numbers, check if all indices are in the same connected component by comparing their roots in DSU.

Code

 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


class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return true;
        unordered_map<int, int> prime_to_idx;
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); };
        auto factor = [](int x) {
            vector<int> res;
            for (int d = 2; d * d <= x; ++d) {
                if (x % d == 0) {
                    res.push_back(d);
                    while (x % d == 0) x /= d;
                }
            }
            if (x > 1) res.push_back(x);
            return res;
        };
        for (int i = 0; i < n; ++i) {
            for (int pf : factor(nums[i])) {
                if (prime_to_idx.count(pf)) {
                    p[find(i)] = find(prime_to_idx[pf]);
                } else {
                    prime_to_idx[pf] = i;
                }
            }
        }
        int root = find(0);
        for (int i = 1; i < n; ++i) {
            if (find(i) != root) return false;
        }
        return true;
    }
};

 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


func canTraverseAllPairs(nums []int) bool {
    n := len(nums)
    if n == 1 {
        return true
    }
    p := make([]int, n)
    for i := range p { p[i] = i }
    var find func(int) int
    find = func(x int) int {
        if p[x] != x { p[x] = find(p[x]) }
        return p[x]
    }
    primeToIdx := map[int]int{}
    factor := func(x int) []int {
        res := []int{}
        for d := 2; d*d <= x; d++ {
            if x%d == 0 {
                res = append(res, d)
                for x%d == 0 { x /= d }
            }
        }
        if x > 1 { res = append(res, x) }
        return res
    }
    for i, v := range nums {
        for _, pf := range factor(v) {
            if idx, ok := primeToIdx[pf]; ok {
                p[find(i)] = find(idx)
            } else {
                primeToIdx[pf] = i
            }
        }
    }
    root := find(0)
    for i := 1; i < n; i++ {
        if find(i) != root {
            return false
        }
    }
    return true
}

 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


class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;
        int[] p = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
        java.util.Map<Integer, Integer> primeToIdx = new java.util.HashMap<>();
        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int x) { return p[x] == x ? x : (p[x] = applyAsInt(p[x])); }
        };
        java.util.function.Function<Integer, java.util.List<Integer>> factor = x -> {
            java.util.List<Integer> res = new java.util.ArrayList<>();
            for (int d = 2; d * d <= x; d++) {
                if (x % d == 0) {
                    res.add(d);
                    while (x % d == 0) x /= d;
                }
            }
            if (x > 1) res.add(x);
            return res;
        };
        for (int i = 0; i < n; i++) {
            for (int pf : factor.apply(nums[i])) {
                if (primeToIdx.containsKey(pf)) {
                    p[find.applyAsInt(i)] = find.applyAsInt(primeToIdx.get(pf));
                } else {
                    primeToIdx.put(pf, i);
                }
            }
        }
        int root = find.applyAsInt(0);
        for (int i = 1; i < n; i++) {
            if (find.applyAsInt(i) != root) return false;
        }
        return true;
    }
}

 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


class Solution {
    fun canTraverseAllPairs(nums: IntArray): Boolean {
        val n = nums.size
        if (n == 1) return true
        val p = IntArray(n) { it }
        fun find(x: Int): Int = if (p[x] == x) x else { p[x] = find(p[x]); p[x] }
        val primeToIdx = mutableMapOf<Int, Int>()
        fun factor(x: Int): List<Int> {
            var x = x
            val res = mutableListOf<Int>()
            var d = 2
            while (d * d <= x) {
                if (x % d == 0) {
                    res.add(d)
                    while (x % d == 0) x /= d
                }
                d++
            }
            if (x > 1) res.add(x)
            return res
        }
        for (i in 0 until n) {
            for (pf in factor(nums[i])) {
                if (primeToIdx.containsKey(pf)) {
                    p[find(i)] = find(primeToIdx[pf]!!)
                } else {
                    primeToIdx[pf] = i
                }
            }
        }
        val root = find(0)
        for (i in 1 until n) {
            if (find(i) != root) return false
        }
        return true
    }
}

 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


class Solution:
    def canTraverseAllPairs(self, nums: list[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True
        p = list(range(n))
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        from collections import defaultdict
        prime_to_idx = dict()
        def factor(x):
            res = set()
            d = 2
            while d * d <= x:
                if x % d == 0:
                    res.add(d)
                    while x % d == 0:
                        x //= d
                d += 1
            if x > 1:
                res.add(x)
            return res
        for i, v in enumerate(nums):
            for pf in factor(v):
                if pf in prime_to_idx:
                    p[find(i)] = find(prime_to_idx[pf])
                else:
                    prime_to_idx[pf] = i
        root = find(0)
        for i in range(1, n):
            if find(i) != root:
                return False
        return True

 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


impl Solution {
    pub fn can_traverse_all_pairs(nums: Vec<i32>) -> bool {
        let n = nums.len();
        if n == 1 { return true; }
        let mut p: Vec<usize> = (0..n).collect();
        fn find(p: &mut Vec<usize>, x: usize) -> usize {
            if p[x] != x { p[x] = find(p, p[x]); }
            p[x]
        }
        use std::collections::HashMap;
        let mut prime_to_idx = HashMap::new();
        fn factor(mut x: i32) -> Vec<i32> {
            let mut res = vec![];
            let mut d = 2;
            while d * d <= x {
                if x % d == 0 {
                    res.push(d);
                    while x % d == 0 { x /= d; }
                }
                d += 1;
            }
            if x > 1 { res.push(x); }
            res
        }
        for (i, &v) in nums.iter().enumerate() {
            for pf in factor(v) {
                if let Some(&idx) = prime_to_idx.get(&pf) {
                    let ri = find(&mut p, i);
                    let rj = find(&mut p, idx);
                    p[ri] = rj;
                } else {
                    prime_to_idx.insert(pf, i);
                }
            }
        }
        let root = find(&mut p, 0);
        for i in 1..n {
            if find(&mut p, i) != root {
                return false;
            }
        }
        true
    }
}

 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


class Solution {
    canTraverseAllPairs(nums: number[]): boolean {
        const n = nums.length;
        if (n === 1) return true;
        const p = Array.from({length: n}, (_, i) => i);
        const find = (x: number): number => p[x] === x ? x : (p[x] = find(p[x]));
        const primeToIdx = new Map<number, number>();
        function factor(x: number): number[] {
            const res: number[] = [];
            for (let d = 2; d * d <= x; d++) {
                if (x % d === 0) {
                    res.push(d);
                    while (x % d === 0) x /= d;
                }
            }
            if (x > 1) res.push(x);
            return res;
        }
        for (let i = 0; i < n; i++) {
            for (const pf of factor(nums[i])) {
                if (primeToIdx.has(pf)) {
                    p[find(i)] = find(primeToIdx.get(pf)!);
                } else {
                    primeToIdx.set(pf, i);
                }
            }
        }
        const root = find(0);
        for (let i = 1; i < n; i++) {
            if (find(i) !== root) return false;
        }
        return true;
    }
}

Complexity

⏰ Time complexity: O(n * sqrt(m)) — For each number, we factorize it up to sqrt(m), where m is the max value in nums.
🧺 Space complexity: O(n + m) — For DSU and prime-to-index mapping.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Union-Find with Prime Factorization#

Intuition#

Approach#

Code#

Complexity#