Replace non coprime numbers in array

Array Math Stack Number Theory

57.7% acceptance

Feb 25, 2026

843

You are given an array of integers nums. Repeatedly find two adjacent non-coprime numbers, replace them with their LCM. Stop when no such pair exists. Two numbers x,y are non-coprime if GCD(x,y) > 1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
    fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a } else { gcd(b, a % b) } }
    let mut stack: Vec<i64> = Vec::new();
    for n in nums {
      let mut cur = n as i64;
      while let Some(&top) = stack.last() {
        let g = gcd(top, cur);
        if g > 1 {
          cur = top / g * cur;  // LCM = top * cur / gcd
          stack.pop();
        } else {
          break;
        }
      }
      stack.push(cur);
    }
    stack.into_iter().map(|x| x as i32).collect()
  }
}