LeetCode Entry

3867. Sum of GCD of Formed Pairs

16.07.2026 medium 2026 kotlin rust

Sum of gcd(min,max) of gcd(x, prefix max)

3867. Sum of GCD of Formed Pairs medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1422

Problem TLDR

Sum of gcd(min,max) of gcd(x, prefix max)

Intuition

The entire algorithm is give, just implement.

Approach

• remember gcd as a/b, bab

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun gcdSum(n: IntArray) = run {
        var max = 0; fun gcd(a: Int, b: Int): Int = if (b==0)a else gcd(b,a%b)
        val g = n.map { max=max(max,it);gcd(max, it) }.sorted()
        (0..<g.size/2).sumOf { i -> 1L*gcd(g[i],g[g.size-1-i]) }
    }

    pub fn gcd_sum(n: Vec<i32>) -> i64 {
        let g = |mut a, mut b| { while b != 0 { (a, b) = (b, a % b); } a };
        let mut m = 0;
        let s: Vec<_> = n.iter().map(|&x| { m = m.max(x); g(m, x) }).sorted().collect();
        (0..s.len() / 2).map(|i| g(s[i], s[s.len() - 1 - i]) as i64).sum()
    }