Sum of gcd of formed pairs

Array Math Two Pointers Simulation Number Theory

65.5% acceptance

Mar 31, 2026

You are given an integer array nums of length n. Construct an array prefixGcd where for each index i: Let mxi = max(nums[0], nums[1], ..., nums[i]). prefixGcd[i] = gcd(nums[i], mxi). After constructing prefixGcd: Sort prefixGcd in non-decreasing order. Form pairs by taking the smallest unpaired element and the largest unpaired element. Repeat this process until no more pairs can be formed. For each formed pair, compute the gcd of the two elements. If n is odd, the middle element in the prefixGcd array remains unpaired and should be ignored. Return an integer denoting the sum of the GCD values of all formed pairs. The term gcd(a, b) denotes the greatest common divisor of a and b.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn gcd_sum(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut prefix_gcd = Vec::with_capacity(n);
    let mut mx = 0i32;
    for &x in &nums {
      mx = mx.max(x);
      prefix_gcd.push(Self::gcd(x, mx));
    }
    prefix_gcd.sort_unstable();
    let mut sum = 0i64;
    let mut lo = 0;
    let mut hi = prefix_gcd.len() - 1;
    while lo < hi {
      sum += Self::gcd(prefix_gcd[lo], prefix_gcd[hi]) as i64;
      lo += 1;
      hi -= 1;
    }
    sum
  }

  fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }
}