2709. Greatest Common Divisor Traversal Solution

The 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 <= 10⁵
1 <= nums[i] <= 10⁵

Approach overview

Problem Overview: You receive an array of integers. You can move between two indices if the gcd(nums[i], nums[j]) > 1. The task is to determine whether every index can be reached from any starting index, meaning the implicit graph formed by these gcd relationships is fully connected.

Approach 1: Graph Traversal by Adjacency List (O(n² log M) time, O(n²) space)

Treat every number as a node in a graph. Compare every pair of values and compute gcd(nums[i], nums[j]). If the result is greater than 1, add an edge between the two indices in an adjacency list. After building the graph, run DFS or BFS to check whether all nodes are reachable from index 0. This approach directly models the graph but performs a gcd calculation for every pair, which becomes expensive for large arrays. It works well for small inputs or when building intuition around graph traversal.

Approach 2: Graph Traversal with Union-Find and Prime Factors (O(n log M) time, O(n + M) space)

Instead of comparing every pair, connect numbers through their prime factors. Factorize each value and track which indices share the same factor. If two numbers contain a common prime factor, union their indices using a Union-Find structure. A hash map from factor → index allows quick unions as factors repeat. This effectively builds the connectivity of the graph without enumerating all edges. Prime factorization takes roughly O(log M) per number using trial division or a smallest-prime-factor sieve from number theory. After processing the entire array, check whether all indices belong to the same set.

The key insight: if two numbers share any prime factor, their gcd is greater than 1, so they belong in the same connected component. Chaining these unions across shared factors builds the full connectivity of the array.

Recommended for interviews: The Union-Find with prime factorization approach. The adjacency-list solution shows you understand the graph model but fails to scale because of the O(n²) pair checks. Interviewers expect the optimized approach that reduces the problem to factor connectivity and merges components using disjoint sets.

Approach 1: Graph Traversal with Union-Find

This approach considers the integer array as a graph where each index is a node. We connect nodes i and j if gcd(nums[i], nums[j]) > 1. Using a union-find data structure, we efficiently manage connected components as we establish connections among indices. The goal is to determine whether all indices are part of a single connected component.

Python

def find(parents, i):
    if parents[i] != i:
        parents[i] = find(parents, parents[i])
    return parents[i]


def union(parents, rank, x, y):
    rootX = find(parents, x)
    rootY = find(parents, y)
    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parents[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parents[rootX] = rootY
        else:
            parents[rootY] = rootX
            rank[rootX] += 1


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def can_traverse_all_pairs(nums):
    n = len(nums)
    parents = list(range(n))
    rank = [0] * n

    for i in range(n):
        for j in range(i + 1, n):
            if gcd(nums[i], nums[j]) > 1:
                union(parents, rank, i, j)

    root = find(parents, 0)
    for i in range(1, n):
        if find(parents, i) != root:
            return False
    return True


if __name__ == "__main__":
    nums = [2, 3, 6]
    print(can_traverse_all_pairs(nums))

Java

import java.util.*;

class UnionFind {
    private int[] root;
    private int[] rank;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

public class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    uf.union(i, j);
                }
            }
        }
        int root = uf.find(0);
        for (int i = 1; i < n; i++) {
            if (uf.find(i) != root) {
                return false;
            }
        }
        return true;
    }

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 3, 6};
        System.out.println(sol.canTraverseAllPairs(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> root;
    vector<int> rank;

    UnionFind(int size) {
        root.resize(size);
        rank.resize(size, 1);
        for (int i = 0; i < size; ++i) {
            root[i] = i;
        }
    }

    int find(int x) {
        if (root[x] == x) return x;
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

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

bool canTraverseAllPairs(vector<int>& nums) {
    int n = nums.size();
    UnionFind uf(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (gcd(nums[i], nums[j]) > 1) {
                uf.unionSet(i, j);
            }
        }
    }
    int root = uf.find(0);
    for (int i = 1; i < n; ++i) {
        if (uf.find(i) != root) return false;
    }
    return true;
}

int main() {
    vector<int> nums = {2, 3, 6};
    cout << (canTraverseAllPairs(nums) ? "true" : "false") << endl;
    return 0;
}

JavaScript

class UnionFind {
    constructor(size) {
        this.root = Array.from({ length: size }, (_, i) => i);
        this.rank = Array(size).fill(1);
    }

    find(x) {
        if (this.root[x] !== x) {
            this.root[x] = this.find(this.root[x]);
        }
        return this.root[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] > this.rank[rootY]) {
                this.root[rootY] = rootX;
            } else if (this.rank[rootX] < this.rank[rootY]) {
                this.root[rootX] = rootY;
            } else {
                this.root[rootY] = rootX;
                this.rank[rootX]++;
            }
        }
    }
}

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

function canTraverseAllPairs(nums) {
    const n = nums.length;
    const uf = new UnionFind(n);

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

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

    return true;
}

console.log(canTraverseAllPairs([2, 3, 6]));

#include <stdio.h>
#include <stdlib.h>

int find(int* parents, int x) {
    if (parents[x] != x) {
        parents[x] = find(parents, parents[x]);
    }
    return parents[x];
}

void union_sets(int* parents, int* rank, int x, int y) {
    int rootX = find(parents, x);
    int rootY = find(parents, y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parents[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parents[rootX] = rootY;
        } else {
            parents[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

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

int canTraverseAllPairs(int* nums, int numsSize) {
    int* parents = (int*)malloc(numsSize * sizeof(int));
    int* rank = (int*)calloc(numsSize, sizeof(int));

    for (int i = 0; i < numsSize; i++) {
        parents[i] = i;
    }

    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (gcd(nums[i], nums[j]) > 1) {
                union_sets(parents, rank, i, j);
            }
        }
    }

    int root = find(parents, 0);
    for (int i = 1; i < numsSize; i++) {
        if (find(parents, i) != root) {
            free(parents);
            free(rank);
            return 0;
        }
    }

    free(parents);
    free(rank);
    return 1;
}

int main() {
    int nums[] = {2, 3, 6};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", canTraverseAllPairs(nums, numsSize) ? "true" : "false");
    return 0;
}

using System;

public class UnionFind {
    private int[] root;
    private int[] rank;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

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

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

public class Solution {
    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public bool CanTraverseAllPairs(int[] nums) {
        int n = nums.Length;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Gcd(nums[i], nums[j]) > 1) {
                    uf.Union(i, j);
                }
            }
        }
        int root = uf.Find(0);
        for (int i = 1; i < n; i++) {
            if (uf.Find(i) != root) {
                return false;
            }
        }
        return true;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] nums = new int[] {2, 3, 6};
        Console.WriteLine(sol.CanTraverseAllPairs(nums));
    }
}

This Python solution implements the union-find method, establishing connections among indices with pairwise GCDs greater than 1. It then checks if all elements form a single connected component by examining the root of each index.

Complexity

The time complexity is O(n^2 * log*(n)), and the space complexity is O(n) for storing the disjoint set structure.

Try this approach in the editor

Approach 2: Graph Traversal by Adjacency List

In this approach, the solution represents the integer array as an adjacency list graph. Each index is considered as a node, and we link them with edges if their GCD is greater than 1. We perform a depth-first search (DFS) or breadth-first search (BFS) to determine the connectivity of the nodes. If all indices are reachable from any starting index, the traversal is possible.

Python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def dfs(v, adj, visited):
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs(u, adj, visited)

def can_traverse_all_pairs(nums):
    n = len(nums)
    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)

    visited = [False] * n
    dfs(0, adj, visited)

    return all(visited)

if __name__ == "__main__":
    nums = [2, 3, 6]
    print(can_traverse_all_pairs(nums))

Java

import java.util.*;

public class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

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

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        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);
                }
            }
        }

        boolean[] visited = new boolean[n];
        dfs(0, adj, visited);

        for (boolean v : visited) {
            if (!v) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 6};
        Solution sol = new Solution();
        System.out.println(sol.canTraverseAllPairs(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

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

void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u, adj, visited);
        }
    }
}

bool canTraverseAllPairs(vector<int>& nums) {
    int n = nums.size();
    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);
            }
        }
    }

    vector<bool> visited(n, false);
    dfs(0, adj, visited);

    for (bool v : visited) {
        if (!v) return false;
    }
    return true;
}

int main() {
    vector<int> nums = {2, 3, 6};
    cout << (canTraverseAllPairs(nums) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

function canTraverseAllPairs(nums) {
    const n = nums.length;
    const adj = Array.from({ length: n }, () => []);

    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 visited = new Array(n).fill(false);

    function dfs(v) {
        visited[v] = true;
        for (const u of adj[v]) {
            if (!visited[u]) {
                dfs(u);
            }
        }
    }

    dfs(0);

    return visited.every(Boolean);
}

console.log(canTraverseAllPairs([2, 3, 6]));

#include <stdio.h>
#include <stdlib.h>

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

void dfs(int node, int* graph[], int* visited, int n) {
    visited[node] = 1;
    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, graph, visited, n);
        }
    }
}

int canTraverseAllPairs(int* nums, int numsSize) {
    int** graph = (int**)malloc(numsSize * sizeof(int*));
    for (int i = 0; i < numsSize; i++) {
        graph[i] = (int*)calloc(numsSize, sizeof(int));
    }

    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (gcd(nums[i], nums[j]) > 1) {
                graph[i][j] = graph[j][i] = 1;
            }
        }
    }

    int* visited = (int*)calloc(numsSize, sizeof(int));
    dfs(0, graph, visited, numsSize);

    for (int i = 0; i < numsSize; i++) {
        if (!visited[i]) {
            for (int j = 0; j < numsSize; j++) free(graph[j]);
            free(graph);
            free(visited);
            return 0;
        }
    }

    for (int i = 0; i < numsSize; i++) free(graph[i]);
    free(graph);
    free(visited);
    return 1;
}

int main() {
    int nums[] = {2, 3, 6};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", canTraverseAllPairs(nums, numsSize) ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    private void Dfs(int node, List<int>[] adj, bool[] visited) {
        visited[node] = true;
        foreach (int neighbor in adj[node]) {
            if (!visited[neighbor]) {
                Dfs(neighbor, adj, visited);
            }
        }
    }

    public bool CanTraverseAllPairs(int[] nums) {
        int n = nums.Length;
        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);
                }
            }
        }

        bool[] visited = new bool[n];
        Dfs(0, adj, visited);

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

    public static void Main() {
        int[] nums = new int[] {2, 3, 6};
        Solution sol = new Solution();
        Console.WriteLine(sol.CanTraverseAllPairs(nums));
    }
}

The Python code represents the array as an adjacency list graph, performing DFS to check whether all nodes are reachable from the first one, verifying the traversal capability between indices.

Complexity

The time complexity is O(n^2) due to building and exploring the graph, with a space complexity of O(n^2) for storing adjacency information.

Try this approach in the editor

Approach 3: Default Approach

const mx = 100010

var p = make([][]int, mx)

func init() {
	for x := 1; x < mx; x++ {
		v := x
		i := 2
		for i <= v/i {
			if v%i == 0 {
				p[x] = append(p[x], i)
				for v%i == 0 {
					v /= i
				}
			}
			i++
		}
		if v > 1 {
			p[x] = append(p[x], v)
		}
	}
}

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func canTraverseAllPairs(nums []int) bool {
	m := slices.Max(nums)
	n := len(nums)
	uf := newUnionFind(m + n + 1)
	for i, x := range nums {
		for _, j := range p[x] {
			uf.union(i, j+n)
		}
	}
	s := map[int]bool{}
	for i := 0; i < n; i++ {
		s[uf.find(i)] = true
	}
	return len(s) == 1
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Graph Traversal with Union-Find	The time complexity is O(n^2 * log*(n)), and the space complexity is O(n) for storing the disjoint set structure.
Graph Traversal by Adjacency List	The time complexity is O(n^2) due to building and exploring the graph, with a space complexity of O(n^2) for storing adjacency information.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Adjacency List + DFS/BFS	O(n² log M)	O(n²)	Small arrays or when demonstrating the direct graph interpretation
Union-Find with Prime Factorization	O(n log M)	O(n + M)	Large inputs and interview settings where optimal connectivity detection is required

Frequently asked questions

Is Greatest Common Divisor Traversal easy or hard?

Greatest Common Divisor Traversal is categorized as a Hard problem. The challenge comes from recognizing that pairwise gcd checks are too slow and transforming the problem into prime-factor connectivity solved with Union-Find.

Greatest Common Divisor Traversal Python/Java solution

Python and Java solutions typically implement a Union-Find class with path compression and union by rank. Each number is factorized, and indices sharing factors are merged in the same set. After processing all numbers, checking that all indices share the same root confirms full traversal.

How to solve Greatest Common Divisor Traversal in O(n)?

Pure O(n) is not typically achievable because each number must be factorized. The closest practical complexity is O(n log M) using prime factorization and Union-Find. Precomputing smallest prime factors with a sieve can make factorization extremely fast in practice.

What is the best approach for Greatest Common Divisor Traversal?

The most efficient approach uses Union-Find combined with prime factorization. Each number is broken into its prime factors, and indices sharing a factor are unioned in a disjoint set. This avoids comparing every pair of numbers and reduces the complexity to about O(n log M), where M is the maximum value in the array.

Is Greatest Common Divisor Traversal asked at Google/Amazon/Meta?

This style of problem frequently appears in interviews at companies like Google, Amazon, and Meta because it combines number theory with graph connectivity. Candidates are expected to recognize that shared prime factors create edges and solve it using Union-Find.

What data structure is used in Greatest Common Divisor Traversal?

The core data structure is Union-Find (Disjoint Set Union) to maintain connected components efficiently. A hash map or array is also used to track the first index seen for each prime factor during factorization.

What is the time complexity of Greatest Common Divisor Traversal?

The optimal solution runs in O(n log M) time due to prime factorization of each number and near-constant Union-Find operations with path compression. A naive adjacency graph approach that checks gcd for every pair costs O(n² log M), which becomes too slow for large inputs.

Greatest Common Divisor Traversal solution and explanation

The problem

Approach overview

Approach 1: Graph Traversal with Union-Find

Approach 2: Graph Traversal by Adjacency List

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Greatest Common Divisor Traversal solution and explanation

The problem

Approach overview

Approach 1: Graph Traversal with Union-Find

Approach 2: Graph Traversal by Adjacency List

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems