Gcd sort of an array

Array Math Union-Find Sorting Number Theory

48.5% acceptance

Feb 25, 2026

531

You are given an integer array nums, and you can perform the following operation any number of times on nums: Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j]. Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn gcd_sort(nums: Vec<i32>) -> bool {
    let max_val = *nums.iter().max().unwrap() as usize;
    
    // Union-Find: connect each number with its prime factors
    let mut parent: Vec<usize> = (0..=max_val).collect();
    let mut rank = vec![0u8; max_val + 1];
    
    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<u8>, a: usize, b: usize) {
      let ra = find(parent, a);
      let rb = find(parent, b);
      if ra == rb {
        return;
      }
      if rank[ra] < rank[rb] {
        parent[ra] = rb;
      } else if rank[ra] > rank[rb] {
        parent[rb] = ra;
      } else {
        parent[rb] = ra;
        rank[ra] += 1;
      }
    }
    
    // Sieve-like: for each number, find prime factors and union with them
    for &num in &nums {
      let n = num as usize;
      let mut x = n;
      let mut d = 2usize;
      while d * d <= x {
        if x % d == 0 {
          union(&mut parent, &mut rank, n, d);
          while x % d == 0 {
            x /= d;
          }
        }
        d += 1;
      }
      if x > 1 {
        union(&mut parent, &mut rank, n, x);
      }
    }
    
    // Check if sorted version can be achieved
    let mut sorted = nums.clone();
    sorted.sort();
    
    for i in 0..nums.len() {
      if find(&mut parent, nums[i] as usize) != find(&mut parent, sorted[i] as usize) {
        return false;
      }
    }
    true
  }
}