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

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Traversal (DFS/BFS) - The problem models indices as nodes and requires checking if all nodes are connected in a single component
Union-Find (Disjoint Set Union) - Optimal solutions use DSU to efficiently track and merge connected components
Greatest Common Divisor (GCD) - Understanding how to compute GCD and recognizing when two numbers share common factors
Prime Factorization - Breaking numbers into prime factors to efficiently determine shared factors between numbers
Sieve of Eratosthenes - Precomputing smallest prime factors enables O(log n) factorization per number

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

public class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        boolean[] visit = new boolean[n];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }

        dfs(0, adj, visit);
        for (boolean node : visit) {
            if (!node) {
                return false;
            }
        }
        return true;
    }

    private void dfs(int node, List<List<Integer>> adj, boolean[] visit) {
        visit[node] = true;
        for (int nei : adj.get(node)) {
            if (!visit[nei]) {
                dfs(nei, adj, visit);
            }
        }
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int n = nums.size();
        vector<bool> visit(n, false);
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (__gcd(nums[i], nums[j]) > 1) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }

        dfs(0, adj, visit);
        for (bool node : visit) {
            if (!node) {
                return false;
            }
        }
        return true;
    }

private:
    void dfs(int node, vector<vector<int>>& adj, vector<bool>& visit) {
        visit[node] = true;
        for (int& nei : adj[node]) {
            if (!visit[nei]) {
                dfs(nei, adj, visit);
            }
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    canTraverseAllPairs(nums) {
        const n = nums.length;
        const visit = new Array(n).fill(false);
        const adj = Array.from({ length: n }, () => []);

        const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj[i].push(j);
                    adj[j].push(i);
                }
            }
        }

        const dfs = (node) => {
            visit[node] = true;
            for (const nei of adj[node]) {
                if (!visit[nei]) {
                    dfs(nei);
                }
            }
        };

        dfs(0);
        return visit.every((node) => node);
    }
}

public class Solution {
    public bool CanTraverseAllPairs(int[] nums) {
        int n = nums.Length;
        bool[] visited = new bool[n];
        List<int>[] adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (GCD(nums[i], nums[j]) > 1) {
                    adj[i].Add(j);
                    adj[j].Add(i);
                }
            }
        }

        void DFS(int node) {
            visited[node] = true;
            foreach (int neighbor in adj[node]) {
                if (!visited[neighbor]) {
                    DFS(neighbor);
                }
            }
        }

        DFS(0);
        foreach (bool v in visited) {
            if (!v) return false;
        }

        return true;
    }

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

func canTraverseAllPairs(nums []int) bool {
    n := len(nums)
    visit := make([]bool, n)
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = []int{}
    }

    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if gcd(nums[i], nums[j]) > 1 {
                adj[i] = append(adj[i], j)
                adj[j] = append(adj[j], i)
            }
        }
    }

    var dfs func(node int)
    dfs = func(node int) {
        visit[node] = true
        for _, nei := range adj[node] {
            if !visit[nei] {
                dfs(nei)
            }
        }
    }

    dfs(0)
    for _, v := range visit {
        if !v {
            return false
        }
    }
    return true
}

class Solution {
    fun canTraverseAllPairs(nums: IntArray): Boolean {
        val n = nums.size
        val visit = BooleanArray(n)
        val adj = Array(n) { mutableListOf<Int>() }

        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

        for (i in 0 until n) {
            for (j in i + 1 until n) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj[i].add(j)
                    adj[j].add(i)
                }
            }
        }

        fun dfs(node: Int) {
            visit[node] = true
            for (nei in adj[node]) {
                if (!visit[nei]) {
                    dfs(nei)
                }
            }
        }

        dfs(0)
        return visit.all { it }
    }
}

class Solution {
    func canTraverseAllPairs(_ nums: [Int]) -> Bool {
        let n = nums.count
        var visit = [Bool](repeating: false, count: n)
        var adj = [[Int]](repeating: [], count: n)

        func gcd(_ a: Int, _ b: Int) -> Int {
            return b == 0 ? a : gcd(b, a % b)
        }

        for i in 0..<n {
            for j in (i + 1)..<n {
                if gcd(nums[i], nums[j]) > 1 {
                    adj[i].append(j)
                    adj[j].append(i)
                }
            }
        }

        func dfs(_ node: Int) {
            visit[node] = true
            for nei in adj[node] {
                if !visit[nei] {
                    dfs(nei)
                }
            }
        }

        dfs(0)
        return visit.allSatisfy { $0 }
    }
}

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()

class UnionFind {
    private int n;
    private int[] Parent;
    private int[] Size;

    public UnionFind(int n) {
        this.n = n;
        this.Parent = new int[n + 1];
        this.Size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            this.Parent[i] = i;
            this.Size[i] = 1;
        }
    }

    public int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    public boolean union(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) return false;
        n--;
        if (Size[pu] < Size[pv]) {
            int temp = pu;
            pu = pv;
            pv = temp;
        }
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }

    public boolean isConnected() {
        return n == 1;
    }
}

public class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        UnionFind uf = new UnionFind(n);
        Map<Integer, Integer> factorIndex = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int f = 2;
            while (f * f <= num) {
                if (num % f == 0) {
                    if (factorIndex.containsKey(f)) {
                        uf.union(i, factorIndex.get(f));
                    } else {
                        factorIndex.put(f, i);
                    }
                    while (num % f == 0) {
                        num /= f;
                    }
                }
                f++;
            }
            if (num > 1) {
                if (factorIndex.containsKey(num)) {
                    uf.union(i, factorIndex.get(num));
                } else {
                    factorIndex.put(num, i);
                }
            }
        }

        return uf.isConnected();
    }
}

class UnionFind {
    /**
     * @constructor
     * @param {number} n
     */
    constructor(n) {
        this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
        this.Size = Array(n + 1).fill(1);
        this.n = n;
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u);
        let pv = this.find(v);
        if (pu === pv) return false;
        this.n--;
        if (this.Size[pu] < this.Size[pv]) {
            [pu, pv] = [pv, pu];
        }
        this.Size[pu] += this.Size[pv];
        this.Parent[pv] = pu;
        return true;
    }

    /**
     * @return {number}
     */
    isConnected() {
        return this.n === 1;
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    canTraverseAllPairs(nums) {
        const n = nums.length;
        const uf = new UnionFind(n);
        const factor_index = new Map();

        for (let i = 0; i < n; i++) {
            let num = nums[i];
            let f = 2;
            while (f * f <= num) {
                if (num % f === 0) {
                    if (factor_index.has(f)) {
                        uf.union(i, factor_index.get(f));
                    } else {
                        factor_index.set(f, i);
                    }
                    while (num % f === 0) {
                        num = Math.floor(num / f);
                    }
                }
                f++;
            }
            if (num > 1) {
                if (factor_index.has(num)) {
                    uf.union(i, factor_index.get(num));
                } else {
                    factor_index.set(num, i);
                }
            }
        }

        return uf.isConnected();
    }
}

public class Solution {
    public class UnionFind {
        public int Count;
        private int[] Parent;
        private int[] Size;

        public UnionFind(int n) {
            Count = n;
            Parent = new int[n];
            Size = new int[n];
            for (int i = 0; i < n; i++) {
                Parent[i] = i;
                Size[i] = 1;
            }
        }

        public int Find(int x) {
            if (Parent[x] != x) {
                Parent[x] = Find(Parent[x]);
            }
            return Parent[x];
        }

        public bool Union(int x, int y) {
            int px = Find(x);
            int py = Find(y);
            if (px == py) return false;
            Count--;
            if (Size[px] < Size[py]) {
                int temp = px;
                px = py;
                py = temp;
            }
            Size[px] += Size[py];
            Parent[py] = px;
            return true;
        }

        public bool IsConnected() {
            return Count == 1;
        }
    }

    public bool CanTraverseAllPairs(int[] nums) {
        int n = nums.Length;
        if (n == 1) return true;
        if (Array.Exists(nums, x => x == 1)) return false;

        UnionFind uf = new UnionFind(n);
        Dictionary<int, int> factorIndex = new Dictionary<int, int>();

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int original = num;
            for (int f = 2; f * f <= num; f++) {
                if (num % f == 0) {
                    if (factorIndex.ContainsKey(f)) {
                        uf.Union(i, factorIndex[f]);
                    } else {
                        factorIndex[f] = i;
                    }
                    while (num % f == 0) {
                        num /= f;
                    }
                }
            }
            if (num > 1) {
                if (factorIndex.ContainsKey(num)) {
                    uf.Union(i, factorIndex[num]);
                } else {
                    factorIndex[num] = 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

class UnionFind {
private:
    vector<int> Parent, Size;

public:
    UnionFind(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionSet(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) {
            return false;
        }
        if (Size[pu] < Size[pv]) {
            swap(pu, pv);
        }
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }
};

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int N = nums.size();
        if (N == 1) {
            return true;
        }
        for (int num : nums) {
            if (num == 1) {
                return false;
            }
        }

        int MAX = *max_element(nums.begin(), nums.end());
        vector<int> sieve(MAX + 1, 0);
        for (int p = 2; p * p <= MAX; p++) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
        }

        UnionFind uf(N + MAX + 1);
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) { // num is prime
                uf.unionSet(i, N + num);
                continue;
            }

            while (num > 1) {
                int prime = sieve[num] != 0 ? sieve[num] : num;
                uf.unionSet(i, N + prime);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        int root = uf.find(0);
        for (int i = 1; i < N; i++) {
            if (uf.find(i) != root) {
                return false;
            }
        }
        return true;
    }
};

class UnionFind {
    /**
     * @constructor
     * @param {number} n
     */
    constructor(n) {
        this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
        this.Size = Array(n + 1).fill(1);
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u);
        let pv = this.find(v);
        if (pu === pv) return false;
        if (this.Size[pu] < this.Size[pv]) {
            [pu, pv] = [pv, pu];
        }
        this.Size[pu] += this.Size[pv];
        this.Parent[pv] = pu;
        return true;
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    canTraverseAllPairs(nums) {
        const N = nums.length;
        if (N === 1) return true;
        if (nums.includes(1)) return false;

        const MAX = Math.max(...nums);
        const sieve = Array(MAX + 1).fill(0);
        for (let p = 2; p * p <= MAX; p++) {
            if (sieve[p] === 0) {
                for (let composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
        }

        const uf = new UnionFind(N + MAX + 1);
        for (let i = 0; i < N; i++) {
            let num = nums[i];
            if (sieve[num] === 0) {
                // num is prime
                uf.union(i, N + num);
                continue;
            }

            while (num > 1) {
                const prime = sieve[num] !== 0 ? sieve[num] : num;
                uf.union(i, N + prime);
                while (num % prime === 0) {
                    num = Math.floor(num / prime);
                }
            }
        }

        const root = uf.find(0);
        for (let i = 1; i < N; i++) {
            if (uf.find(i) !== root) {
                return false;
            }
        }
        return true;
    }
}

public class UnionFind {
    public int[] Parent;
    public int[] Size;

    public UnionFind(int n) {
        Parent = new int[n];
        Size = new int[n];
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

    public int Find(int x) {
        if (Parent[x] != x) {
            Parent[x] = Find(Parent[x]);
        }
        return Parent[x];
    }

    public bool Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
        if (px == py) return false;
        if (Size[px] < Size[py]) {
            int temp = px;
            px = py;
            py = temp;
        }
        Parent[py] = px;
        Size[px] += Size[py];
        return true;
    }
}

public class Solution {
    public bool CanTraverseAllPairs(int[] nums) {
        int n = nums.Length;
        if (n == 1) return true;
        if (Array.Exists(nums, x => x == 1)) return false;

        int maxVal = nums.Max();
        int[] sieve = new int[maxVal + 1];
        for (int i = 2; i * i <= maxVal; i++) {
            if (sieve[i] == 0) {
                for (int j = i * i; j <= maxVal; j += i) {
                    if (sieve[j] == 0) sieve[j] = i;
                }
            }
        }

        UnionFind uf = new UnionFind(n + maxVal + 1);

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (sieve[num] == 0) {
                uf.Union(i, n + num);
                continue;
            }

            while (num > 1) {
                int prime = sieve[num] != 0 ? sieve[num] : num;
                uf.Union(i, n + prime);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        int root = uf.Find(0);
        for (int i = 1; i < n; i++) {
            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

public class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int N = nums.length;
        if (N == 1) return true;
        for (int num : nums) {
            if (num == 1) return false;
        }

        int MAX = Arrays.stream(nums).max().getAsInt();
        int[] sieve = new int[MAX + 1];
        for (int p = 2; p * p <= MAX; p++) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            adj.putIfAbsent(i, new ArrayList<>());

            if (sieve[num] == 0) {
                adj.putIfAbsent(N + num, new ArrayList<>());
                adj.get(i).add(N + num);
                adj.get(N + num).add(i);
                continue;
            }

            while (num > 1) {
                int prime = (sieve[num] == 0) ? num : sieve[num];
                adj.putIfAbsent(N + prime, new ArrayList<>());
                adj.get(i).add(N + prime);
                adj.get(N + prime).add(i);
                while (num % prime == 0) num /= prime;
            }
        }

        Set<Integer> visited = new HashSet<>();
        dfs(0, adj, visited);
        for (int i = 0; i < N; i++) {
            if (!visited.contains(i)) return false;
        }
        return true;
    }

    private void dfs(int node, Map<Integer, List<Integer>> adj, Set<Integer> visited) {
        visited.add(node);
        for (int neighbor : adj.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, adj, visited);
            }
        }
    }
}

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int N = nums.size();
        if (N == 1) return true;
        if (find(nums.begin(), nums.end(), 1) != nums.end()) return false;

        int MAX = *max_element(nums.begin(), nums.end());
        vector<int> sieve(MAX + 1, 0);
        for (int p = 2; p * p <= MAX; p++) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
        }

        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (!adj.count(i)) adj[i] = {};

            if (sieve[num] == 0) {
                adj[N + num].push_back(i);
                adj[i].push_back(N + num);
                continue;
            }

            while (num > 1) {
                int prime = (sieve[num] == 0) ? num : sieve[num];
                adj[N + prime].push_back(i);
                adj[i].push_back(N + prime);
                while (num % prime == 0) num /= prime;
            }
        }

        unordered_set<int> visited;
        dfs(0, adj, visited);
        for (int i = 0; i < N; i++) {
            if (visited.find(i) == visited.end()) return false;
        }
        return true;
    }

private:
    void dfs(int node, unordered_map<int, vector<int>>& adj, unordered_set<int>& visited) {
        visited.insert(node);
        for (int& neighbor : adj[node]) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor, adj, visited);
            }
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    canTraverseAllPairs(nums) {
        const N = nums.length;
        if (N === 1) return true;
        if (nums.includes(1)) return false;

        const MAX = Math.max(...nums);
        const sieve = new Array(MAX + 1).fill(0);
        for (let p = 2; p * p <= MAX; p++) {
            if (sieve[p] === 0) {
                for (let composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
        }

        const adj = new Map();
        for (let i = 0; i < N; i++) {
            if (!adj.has(i)) adj.set(i, []);
            let num = nums[i];

            if (sieve[num] === 0) {
                if (!adj.has(N + num)) adj.set(N + num, []);
                adj.get(i).push(N + num);
                adj.get(N + num).push(i);
                continue;
            }

            while (num > 1) {
                const prime = sieve[num] === 0 ? num : sieve[num];
                if (!adj.has(N + prime)) adj.set(N + prime, []);
                adj.get(i).push(N + prime);
                adj.get(N + prime).push(i);
                while (num % prime === 0) num = Math.floor(num / prime);
            }
        }

        const visited = new Set();
        const dfs = (node) => {
            visited.add(node);
            for (const neighbor of adj.get(node) || []) {
                if (!visited.has(neighbor)) {
                    dfs(neighbor);
                }
            }
        };

        dfs(0);
        for (let i = 0; i < N; i++) {
            if (!visited.has(i)) return false;
        }
        return true;
    }
}

public class Solution {
    public bool CanTraverseAllPairs(int[] nums) {
        int N = nums.Length;
        if (N == 1) return true;
        if (Array.Exists(nums, num => num == 1)) return false;

        int MAX = nums.Max();
        int[] sieve = new int[MAX + 1];
        for (int p = 2; p * p <= MAX; p++) {
            if (sieve[p] == 0) {
                for (int mult = p * p; mult <= MAX; mult += p) {
                    if (sieve[mult] == 0) {
                        sieve[mult] = p;
                    }
                }
            }
        }

        Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) {
                AddEdge(adj, i, N + num);
                continue;
            }
            while (num > 1) {
                int prime = sieve[num] != 0 ? sieve[num] : num;
                AddEdge(adj, i, N + prime);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        HashSet<int> visited = new HashSet<int>();
        DFS(0, adj, visited);

        for (int i = 0; i < N; i++) {
            if (!visited.Contains(i)) return false;
        }

        return true;
    }

    private void AddEdge(Dictionary<int, List<int>> adj, int u, int v) {
        if (!adj.ContainsKey(u)) adj[u] = new List<int>();
        if (!adj.ContainsKey(v)) adj[v] = new List<int>();
        adj[u].Add(v);
        adj[v].Add(u);
    }

    private void DFS(int node, Dictionary<int, List<int>> adj, HashSet<int> visited) {
        visited.Add(node);
        if (!adj.ContainsKey(node)) return;
        foreach (int nei in adj[node]) {
            if (!visited.Contains(nei)) {
                DFS(nei, adj, visited);
            }
        }
    }
}

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

public class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int N = nums.length;
        if (N == 1) return true;
        for (int num : nums) {
            if (num == 1) return false;
        }

        int MAX = Arrays.stream(nums).max().getAsInt();
        int[] sieve = new int[MAX + 1];
        int p = 2;
        while (p * p <= MAX) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
            p++;
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) { // num is prime
                adj.computeIfAbsent(i, k -> new ArrayList<>()).add(N + num);
                adj.computeIfAbsent(N + num, k -> new ArrayList<>()).add(i);
                continue;
            }

            while (num > 1) {
                int prime = (sieve[num] != 0) ? sieve[num] : num;
                adj.computeIfAbsent(i, k -> new ArrayList<>()).add(N + prime);
                adj.computeIfAbsent(N + prime, k -> new ArrayList<>()).add(i);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited.add(0);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int nei : adj.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(nei)) {
                    visited.add(nei);
                    queue.add(nei);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if (!visited.contains(i)) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int N = nums.size();
        if (N == 1) return true;
        if (find(nums.begin(), nums.end(), 1) != nums.end()) return false;

        int MAX = *max_element(nums.begin(), nums.end());
        vector<int> sieve(MAX + 1, 0);
        int p = 2;
        while (p * p <= MAX) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
            p++;
        }

        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) { // num is prime
                adj[i].push_back(N + num);
                adj[N + num].push_back(i);
                continue;
            }

            while (num > 1) {
                int prime = (sieve[num] != 0) ? sieve[num] : num;
                adj[i].push_back(N + prime);
                adj[N + prime].push_back(i);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        unordered_set<int> visited;
        queue<int> q;
        q.push(0);
        visited.insert(0);

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int& nei : adj[node]) {
                if (visited.find(nei) == visited.end()) {
                    visited.insert(nei);
                    q.push(nei);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if (visited.find(i) == visited.end()) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    canTraverseAllPairs(nums) {
        const N = nums.length;
        if (N === 1) return true;
        if (nums.includes(1)) return false;

        const MAX = Math.max(...nums);
        const sieve = Array(MAX + 1).fill(0);
        let p = 2;
        while (p * p <= MAX) {
            if (sieve[p] === 0) {
                for (let composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
            p++;
        }

        const adj = new Map();
        for (let i = 0; i < N; i++) {
            let num = nums[i];
            if (sieve[num] === 0) {
                // num is prime
                if (!adj.has(i)) adj.set(i, []);
                if (!adj.has(N + num)) adj.set(N + num, []);
                adj.get(i).push(N + num);
                adj.get(N + num).push(i);
                continue;
            }

            while (num > 1) {
                const prime = sieve[num] !== 0 ? sieve[num] : num;
                if (!adj.has(i)) adj.set(i, []);
                if (!adj.has(N + prime)) adj.set(N + prime, []);
                adj.get(i).push(N + prime);
                adj.get(N + prime).push(i);
                while (num % prime === 0) {
                    num = Math.floor(num / prime);
                }
            }
        }

        const visited = new Set();
        const queue = new Queue([0]);
        visited.add(0);

        while (!queue.isEmpty()) {
            const node = queue.pop();
            if (adj.has(node)) {
                for (const nei of adj.get(node)) {
                    if (!visited.has(nei)) {
                        visited.add(nei);
                        queue.push(nei);
                    }
                }
            }
        }

        for (let i = 0; i < N; i++) {
            if (!visited.has(i)) {
                return false;
            }
        }
        return true;
    }
}

public class Solution {
    public bool CanTraverseAllPairs(int[] nums) {
        int N = nums.Length;
        if (N == 1) return true;
        if (nums.Contains(1)) return false;

        int MAX = nums.Max();
        int[] sieve = new int[MAX + 1];
        for (int p = 2; p * p <= MAX; p++) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    if (sieve[composite] == 0) {
                        sieve[composite] = p;
                    }
                }
            }
        }

        Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) {
                AddEdge(adj, i, N + num);
                continue;
            }

            while (num > 1) {
                int prime = sieve[num] != 0 ? sieve[num] : num;
                AddEdge(adj, i, N + prime);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        HashSet<int> visited = new HashSet<int>();
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        visited.Add(0);

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            if (!adj.ContainsKey(node)) continue;
            foreach (int nei in adj[node]) {
                if (!visited.Contains(nei)) {
                    visited.Add(nei);
                    queue.Enqueue(nei);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if (!visited.Contains(i)) return false;
        }

        return true;
    }

    private void AddEdge(Dictionary<int, List<int>> adj, int u, int v) {
        if (!adj.ContainsKey(u)) adj[u] = new List<int>();
        if (!adj.ContainsKey(v)) adj[v] = new List<int>();
        adj[u].Add(v);
        adj[v].Add(u);
    }
}

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.