Welcome to Subscribe On Youtube

3867. Sum of GCD of Formed Pairs

Description

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.

 

Example 1:

Input: nums = [2,6,4]

Output: 2

Explanation:

Construct prefixGcd:

i nums[i] mxi prefixGcd[i]
0 2 2 2
1 6 6 6
2 4 6 2

prefixGcd = [2, 6, 2]. After sorting, it forms [2, 2, 6].

Pair the smallest and largest elements: gcd(2, 6) = 2. The remaining middle element 2 is ignored. Thus, the sum is 2.

Example 2:

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

Output: 5

Explanation:

Construct prefixGcd:

i nums[i] mxi prefixGcd[i]
0 3 3 3
1 6 6 6
2 2 6 2
3 8 8 8

prefixGcd = [3, 6, 2, 8]. After sorting, it forms [2, 3, 6, 8].

Form pairs: gcd(2, 8) = 2 and gcd(3, 6) = 3. Thus, the sum is 2 + 3 = 5.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 10​​​​​​​9

Solutions

Solution 1: Simulation

We simulate according to the problem description.

We create an array $\textit{prefixGcd}$ to store the value for each index $i$. We also maintain a variable $mx$ to track the current maximum value. For each element $nums[i]$, we update $mx$ and compute the value of $\textit{prefixGcd}[i]$. Then we sort $\textit{prefixGcd}$ and calculate the sum of GCDs of the formed pairs.

The time complexity is $O(n \log M + n \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the array and $M$ is the maximum value in the array.

  • 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);
        }

        Arrays.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;
    }
}


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

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

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

        long long ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans += gcd(prefix_gcd[i], prefix_gcd[n - i - 1]);
        }

        return ans;
    }
};


  • class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        n = len(nums)
        prefix_gcd = [0] * n
        mx = 0
        for i, x in enumerate(nums):
            mx = max(mx, x)
            prefix_gcd[i] = gcd(x, mx)
        prefix_gcd.sort()
        return sum(gcd(prefix_gcd[i], prefix_gcd[-i - 1]) for i in range(n // 2))


  • func gcdSum(nums []int) int64 {
	n := len(nums)
	prefixGcd := make([]int, n)
	mx := 0

	for i, x := range nums {
		if x > mx {
			mx = x
		}
		prefixGcd[i] = gcd(x, mx)
	}

	sort.Ints(prefixGcd)

	var ans int64
	for i := 0; i < n/2; i++ {
		ans += int64(gcd(prefixGcd[i], prefixGcd[n-i-1]))
	}

	return ans
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}


  • function gcdSum(nums: number[]): number {
    const n = nums.length;
    const prefixGcd: number[] = new Array(n);
    let mx = 0;

    for (let i = 0; i < n; i++) {
        const x = nums[i];
        mx = Math.max(mx, x);
        prefixGcd[i] = gcd(x, mx);
    }

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

    let ans = 0;
    for (let i = 0; i < n >> 1; i++) {
        ans += gcd(prefixGcd[i], prefixGcd[n - i - 1]);
    }

    return ans;
}

function gcd(a: number, b: number): number {
    while (b !== 0) {
        const t = a % b;
        a = b;
        b = t;
    }
    return a;
}

All Problems

All Solutions