3867. Sum of GCD of Formed Pairs

import java.util.*;
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++) {
            mx = Math.max(mx, nums[i]);
            prefixGcd[i] = gcd(nums[i], mx);
        }
        Arrays.sort(prefixGcd);
        long ans = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            ans += gcd(prefixGcd[l], prefixGcd[r]);
            l++;
            r--;
        }
        return ans;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

class Solution:
    def gcdSum(self, nums: List[int]) -> int:
        from math import gcd

        prefix_gcd = []
        mx = 0

        for num in nums:
            mx = max(mx, num)
            prefix_gcd.append(gcd(num, mx))

        prefix_gcd.sort()

        ans = 0
        l, r = 0, len(prefix_gcd) - 1

        while l < r:
            ans += gcd(prefix_gcd[l], prefix_gcd[r])
            l += 1
            r -= 1

        return ans

class Solution {
public:
    long long gcdSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefixGcd(n);

        int mx = 0;
        for (int i = 0; i < n; i++) {
            mx = max(mx, nums[i]);
            prefixGcd[i] = gcd(nums[i], mx);
        }

        sort(prefixGcd.begin(), prefixGcd.end());

        long long ans = 0;
        int l = 0, r = n - 1;

        while (l < r) {
            ans += gcd(prefixGcd[l], prefixGcd[r]);
            l++;
            r--;
        }

        return ans;
    }
};

var gcdSum = function(nums) {
    const gcd = (a, b) => {
        while (b !== 0) {
            let t = a % b;
            a = b;
            b = t;
        }
        return a;
    };

    const prefixGcd = [];
    let mx = 0;

    for (const num of nums) {
        mx = Math.max(mx, num);
        prefixGcd.push(gcd(num, mx));
    }

    prefixGcd.sort((a, b) => a - b);

    let ans = 0;
    let l = 0, r = prefixGcd.length - 1;

    while (l < r) {
        ans += gcd(prefixGcd[l], prefixGcd[r]);
        l++;
        r--;
    }

    return ans;
};