Minimize array sum using divisible replacements

31.1% acceptance

May 13, 2026

You are given an integer array nums. You can perform the following operation any number of times: Choose two indices a and b such that nums[a] % nums[b] == 0. Replace nums[a] with nums[b]. Return the minimum possible sum of the array after performing any number of operations.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_array_sum(nums: Vec<i32>) -> i64 {
    let max_v = *nums.iter().max().unwrap() as usize;
    let mut in_set = vec![false; max_v + 1];
    for &x in &nums {
      in_set[x as usize] = true;
    }
    let mut mark = vec![0i32; max_v + 1];
    for y in 1..=max_v {
      if !in_set[y] { continue; }
      let mut v = y;
      while v <= max_v {
        if in_set[v] && mark[v] == 0 {
          mark[v] = y as i32;
        }
        v += y;
      }
    }
    nums.iter().map(|&x| mark[x as usize] as i64).sum()
  }
}