3867. Sum of GCD of Formed Pairs

Array
Math
Number Theory
Sorting
Two Pointers
Simulation

TIME

O(n log n + n log V)

SPACE

O(n)

Intuition

The problem spells out the procedure, so just follow it efficiently. Two observations keep it linear-ish:

The running maximum mx_i is computed in a single left-to-right pass, no need to recompute a max per index.
"Repeatedly pair the smallest unpaired with the largest unpaired" on a sorted array is exactly a two-pointer walk inward from both ends. The odd middle element is skipped for free when the pointers cross.

Approach

Sweep left to right maintaining mx = running max; set prefixGcd[i] = gcd(nums[i], mx).
Sort prefixGcd.
Two pointers l = 0, r = n - 1; while l < r, add gcd(a[l], a[r]) to the answer, then l++, r--.
Return the sum.

Complexity

Time: O(n log n + n log V), the sort dominates; each gcd is O(log V)
Space: O(n), the prefixGcd array

Edge Cases

n = 1 → no pairs can be formed → 0
n odd → the middle element is skipped automatically when l == r
Note gcd(nums[i], mx_i) == nums[i] whenever nums[i] is itself the running max
Sum can reach ~n · 10^9 ≈ 10^14 → use long in Java

Code

from typing import List
from math import gcd


class Solution:
    def sumOfGcdPairs(self, nums: List[int]) -> int:
        """
        3867. Sum of GCD of Formed Pairs
        Time: O(n log n + n log V)
        Space: O(n)
        """
        prefix_gcd = []
        mx = 0
        for x in nums:
            mx = max(mx, x)          # running maximum
            prefix_gcd.append(gcd(x, mx))

        prefix_gcd.sort()

        # Pair smallest with largest, walking inward.
        total = 0
        l, r = 0, len(prefix_gcd) - 1
        while l < r:
            total += gcd(prefix_gcd[l], prefix_gcd[r])
            l += 1
            r -= 1
        return total

import java.util.Arrays;

/**
 * 3867. Sum of GCD of Formed Pairs
 * Time: O(n log n + n log V)
 * Space: O(n)
 */
class Solution {
    public long sumOfGcdPairs(int[] nums) {
        int n = nums.length;
        int[] prefixGcd = new int[n];
        int mx = 0;
        for (int i = 0; i < n; i++) {
            mx = Math.max(mx, nums[i]); // running maximum
            prefixGcd[i] = gcd(nums[i], mx);
        }

        Arrays.sort(prefixGcd);

        // Pair smallest with largest, walking inward.
        long total = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            total += gcd(prefixGcd[l], prefixGcd[r]);
            l++;
            r--;
        }
        return total;
    }

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