DDSA Solutions

3867. Sum of GCD of Formed Pairs

MediumView on LeetCode
ArrayMathNumber TheorySortingTwo Pointers
Time: O(n log n + n log M)
Space: O(n)

Problem Overview

The problem defines the pairs for you: first build prefixGcd[i] = gcd(nums[i], max of the prefix ending at i), then sort that array and pair the smallest leftover with the largest leftover until nothing remains (odd middle ignored).

Intuition

The problem defines the pairs for you: first build prefixGcd[i] = gcd(nums[i], max of the prefix ending at i), then sort that array and pair the smallest leftover with the largest leftover until nothing remains (odd middle ignored). So simulate the construction, sort, and sum gcd of end-pairs — no combinatorial search needed.

Algorithm

  1. 1Scan left to right keeping running max mx; set prefixGcd[i] = gcd(nums[i], mx).
  2. 2Sort prefixGcd ascending.
  3. 3For i = 0 … n/2 − 1: add gcd(prefixGcd[i], prefixGcd[n−1−i]) to the answer.
  4. 4If n is odd, the middle element is never paired — the loop naturally skips it.
  5. 5Return the sum as a long.

Example Walkthrough

Input: nums = [3, 6, 2, 8]

  1. 1.prefix maxes: 3,6,6,8 → prefixGcd = [gcd(3,3), gcd(6,6), gcd(2,6), gcd(8,8)] = [3,6,2,8].
  2. 2.Sort → [2, 3, 6, 8].
  3. 3.Pairs: gcd(2,8)=2 and gcd(3,6)=3.
  4. 4.Sum = 5.

Output: 5

Common Pitfalls

  • •Update mx before computing gcd(nums[i], mx) — mx must include nums[i].
  • •Pair after sorting ends, not adjacent sorted neighbors.
  • •Use long for the answer; many pairs of large GCDs can overflow int.
  • •When n is odd the middle sorted value contributes nothing — do not add it alone.
3867.cs
C#
// Approach: Build prefixGcd[i] = gcd(nums[i], max(nums[0..i])). Sort ascending, then
// pair smallest with largest (two pointers from ends); sum gcd of each pair. Odd middle ignored.
// Time: O(n log n + n log M) Space: O(n) where M = max(nums)
public class Solution
{
    public long GcdSum(int[] nums)
    {
        int n = nums.Length;
        int[] prefixGcd = new int[n];
        int mx = 0;

        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            mx = Math.Max(mx, x);
            prefixGcd[i] = Gcd(x, mx);
        }

        Array.Sort(prefixGcd);

        long ans = 0;
        for (int i = 0; i < n / 2; i++)
            ans += Gcd(prefixGcd[i], prefixGcd[n - i - 1]);

        return ans;
    }

    private int Gcd(int a, int b)
    {
        while (b != 0)
        {
            int t = a % b;
            a = b;
            b = t;
        }

        return a;
    }
}
Was this solution helpful?

Related Problems