LeetCode Problem 3867

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers, Simulation, Number Theory

Solution

LeetCode 3867 - Sum of GCD of Formed Pairs

Problem Understanding

We are given an integer array nums of length n.

For every index i, we first compute:

• mxi, the maximum value among nums[0...i]
• prefixGcd[i] = gcd(nums[i], mxi)

This creates a new array called prefixGcd.

After that, we sort prefixGcd in non-decreasing order. Once sorted, we repeatedly form pairs using the smallest remaining element and the largest remaining element. In other words:

• First pair: first and last element
• Second pair: second and second-last element
• And so on

For every pair (a, b), we compute gcd(a, b) and add it to the answer.

If the array length is odd, one middle element remains unpaired after all pairings are formed. That element contributes nothing to the result and should simply be ignored.

The task is to return the sum of the GCD values of all formed pairs.

The constraints are important:

• n can be as large as 100,000
• nums[i] can be as large as 10^9

This immediately tells us that any algorithm with quadratic behavior is impossible. We need something close to O(n log n).

A key observation is that prefixGcd[i] = gcd(nums[i], mxi). Since mxi is the maximum value seen so far, and mxi >= nums[i], every prefixGcd[i] is a divisor of nums[i], and therefore:

prefixGcd[i] <= nums[i] <= 10^9

Some important edge cases include:

• A single-element array, where no pair can be formed.
• Arrays where all elements are equal.
• Strictly increasing arrays, where every element equals the current prefix maximum.
• Strictly decreasing arrays, where many GCD values may become small.
• Very large values near 10^9, requiring efficient GCD computation.

Approaches

Brute Force

The most direct solution is to follow the statement literally.

First, build the prefixGcd array by maintaining the current prefix maximum and computing a GCD for every position.

Next, sort the resulting array.

Finally, use two pointers, one at the beginning and one at the end of the sorted array. For every pair, compute the GCD and add it to the answer.

This approach is already quite efficient because the problem itself only requires one sort and one pass through the array.

Key Insight

The crucial observation is that after constructing prefixGcd, the pairing process is completely deterministic.

Once the array is sorted:

• Smallest element pairs with largest
• Second smallest pairs with second largest
• And so on

There is no optimization problem or choice involved.

Therefore, we only need to:

1. Construct prefixGcd.
2. Sort it.
3. Sum the GCD of mirrored positions.

Since sorting dominates the running time, the optimal complexity becomes O(n log n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Direct simulation of the required process
Optimal	O(n log n)	O(n)	Same idea, sorting is unavoidable and dominates runtime

In practice, the brute force simulation is already optimal because the problem structure does not allow us to avoid sorting.

Algorithm Walkthrough

1. Initialize an empty array prefixGcd.
2. Maintain a variable currentMax, representing the maximum value seen so far.
3. Iterate through nums.

• Update currentMax = max(currentMax, nums[i]).
• Compute gcd(nums[i], currentMax).
• Append the result to prefixGcd.

4. Sort prefixGcd in non-decreasing order.
5. Initialize two pointers:

• left = 0
• right = n - 1

6. Initialize answer = 0.
7. While left < right:

• Compute gcd(prefixGcd[left], prefixGcd[right]).
• Add it to answer.
• Increment left.
• Decrement right.

8. When the pointers meet or cross, all possible pairs have been processed.
9. Return answer.

Why it works

The construction phase exactly follows the definition of prefixGcd.

After sorting, the problem explicitly requires pairing the smallest remaining value with the largest remaining value. Using two pointers on the sorted array reproduces this process exactly. Since every required pair is processed once and only once, the computed sum is precisely the sum requested by the problem.

Python Solution

from math import gcd

class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        prefix_gcd = []
        current_max = 0

        for value in nums:
            current_max = max(current_max, value)
            prefix_gcd.append(gcd(value, current_max))

        prefix_gcd.sort()

        left = 0
        right = len(prefix_gcd) - 1
        answer = 0

        while left < right:
            answer += gcd(prefix_gcd[left], prefix_gcd[right])
            left += 1
            right -= 1

        return answer

The implementation follows the algorithm directly.

The first loop constructs the prefix_gcd array while maintaining the running maximum. Python's built-in math.gcd performs each GCD computation efficiently.

After sorting, a classic two-pointer technique is used. The left pointer always references the smallest remaining element, while the right pointer references the largest remaining element. Their GCD is added to the answer, and both pointers move inward.

If the array length is odd, the middle element is automatically skipped because the loop condition is left < right.

Go Solution

package main

import "sort"

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

func gcdSum(nums []int) int64 {
	n := len(nums)

	prefixGcd := make([]int, 0, n)
	currentMax := 0

	for _, value := range nums {
		if value > currentMax {
			currentMax = value
		}
		prefixGcd = append(prefixGcd, gcd(value, currentMax))
	}

	sort.Ints(prefixGcd)

	var answer int64

	left := 0
	right := n - 1

	for left < right {
		answer += int64(gcd(prefixGcd[left], prefixGcd[right]))
		left++
		right--
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

A custom Euclidean GCD function is used. The answer is stored as int64 because the required function signature returns int64, and the sum of many GCD values can exceed the range of a 32-bit integer.

Slices are used to store the prefixGcd array, and sort.Ints performs the required sorting.

Worked Examples

Example 1

Input

nums = [2, 6, 4]

Step 1: Build prefixGcd

i	nums[i]	currentMax	gcd(nums[i], currentMax)
0	2	2	2
1	6	6	6
2	4	6	2

Result:

prefixGcd = [2, 6, 2]

Step 2: Sort

[2, 2, 6]

Step 3: Form pairs

Pair	GCD
(2, 6)	2

Middle element:

2

Ignored.

Answer:

2

Example 2

Input

nums = [3, 6, 2, 8]

Step 1: Build prefixGcd

i	nums[i]	currentMax	gcd(nums[i], currentMax)
0	3	3	3
1	6	6	6
2	2	6	2
3	8	8	8

Result:

prefixGcd = [3, 6, 2, 8]

Step 2: Sort

[2, 3, 6, 8]

Step 3: Form pairs

Pair	GCD
(2, 8)	2
(3, 6)	3

Answer:

2 + 3 = 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Constructing the array is O(n), sorting dominates
Space	O(n)	Storage of the prefixGcd array

The construction phase performs one GCD computation per element and runs in linear time. The sorting step requires O(n log n) time and dominates the overall complexity. The pairing phase is another linear pass. Therefore, the total complexity is O(n log n) with O(n) auxiliary space.

Test Cases

from math import gcd

s = Solution()

assert s.gcdSum([2, 6, 4]) == 2          # example 1
assert s.gcdSum([3, 6, 2, 8]) == 5       # example 2

assert s.gcdSum([5]) == 0                # single element, no pairs

assert s.gcdSum([7, 7]) == 7             # two equal elements

assert s.gcdSum([4, 4, 4, 4]) == 8       # all elements equal

assert s.gcdSum([1, 2, 3, 4, 5]) == 3    # increasing sequence

assert s.gcdSum([10, 8, 6, 4, 2]) == 4   # decreasing sequence

assert s.gcdSum([1000000000, 1000000000]) == 1000000000  # large values

assert s.gcdSum([9, 3, 6, 12, 15]) == 6  # mixed divisibility

assert s.gcdSum([1, 1, 1, 1, 1, 1]) == 3 # many identical small values

Test Summary

Test	Why
[2,6,4]	First official example
[3,6,2,8]	Second official example
[5]	No pair can be formed
[7,7]	Smallest non-trivial case
[4,4,4,4]	All values identical
[1,2,3,4,5]	Strictly increasing sequence
[10,8,6,4,2]	Strictly decreasing sequence
[1000000000,1000000000]	Maximum value stress test
[9,3,6,12,15]	Mixed GCD relationships
[1,1,1,1,1,1]	Repeated minimal values

Edge Cases

Single Element Array

When n = 1, no pair can be formed because there is only one element after sorting. A common bug is attempting to process the middle element as a pair. The two-pointer loop uses the condition left < right, so the loop never executes and the answer correctly remains 0.

Odd Length Arrays

For odd-length arrays, one element remains in the center after all pairings are formed. The problem explicitly states that this element must be ignored. The two-pointer approach naturally handles this situation because the loop stops when left == right, leaving the middle element unprocessed.

All Elements Equal

Suppose every value is the same, such as [4,4,4,4]. Then every prefix maximum is also 4, making every prefixGcd value equal to 4. Every formed pair therefore contributes 4 to the answer. The implementation handles this correctly because sorting identical values changes nothing and the GCD computations remain valid.

Very Large Values

Values can be as large as 10^9. Any approach that attempts factorization would be unnecessarily expensive. The implementation relies only on the Euclidean algorithm, whose complexity is logarithmic in the magnitude of the numbers, making it efficient even for the largest allowed inputs.

Strictly Increasing Arrays

When the array is strictly increasing, every element becomes the new prefix maximum. Therefore gcd(nums[i], currentMax) = nums[i], and prefixGcd becomes identical to the original array. The algorithm still works correctly because it treats the resulting values exactly according to the pairing rules.