Greatest common divisor traversal

Array Math Union-Find Number Theory

41.8% acceptance

Feb 25, 2026

860

143

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_traverse_all_pairs(nums: Vec<i32>) -> bool {
    let n = nums.len();
    if n == 1 { return true; }

    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0usize; n];

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x { parent[x] = find(parent, parent[x]); }
      parent[x]
    }

    fn union(parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) {
      let (rx, ry) = (find(parent, x), find(parent, y));
      if rx == ry { return; }
      if rank[rx] < rank[ry] { parent[rx] = ry; }
      else if rank[rx] > rank[ry] { parent[ry] = rx; }
      else { parent[ry] = rx; rank[rx] += 1; }
    }

    // Map prime -> first index that has this prime factor
    let mut prime_to_idx: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();

    for (i, &num) in nums.iter().enumerate() {
      let mut x = num as usize;
      let mut p = 2usize;
      while p * p <= x {
        if x % p == 0 {
          if let Some(&j) = prime_to_idx.get(&p) {
            union(&mut parent, &mut rank, i, j);
          } else {
            prime_to_idx.insert(p, i);
          }
          while x % p == 0 { x /= p; }
        }
        p += 1;
      }
      if x > 1 {
        if let Some(&j) = prime_to_idx.get(&x) {
          union(&mut parent, &mut rank, i, j);
        } else {
          prime_to_idx.insert(x, i);
        }
      }
    }

    let root = find(&mut parent, 0);
    (1..n).all(|i| find(&mut parent, i) == root)
  }
}