3867. Sum of GCD of Formed Pairs

MediumArrayMathTwo PointersNumber TheorySimulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

Your task is to build a new array called prefixGcd, and then perform a pairing operation on it to compute a final sum. Let's break this down into steps.

Step 1: Construct the prefixGcd array.

For each index i in nums:

First, find the maximum value among all elements from the start up to index i. Call this mxᵢ, where mxᵢ = max(nums[0], nums[1], ..., nums[i]).
Then, compute prefixGcd[i] = gcd(nums[i], mxᵢ), which is the greatest common divisor of the current element nums[i] and the running maximum mxᵢ.

Step 2: Sort prefixGcd.

Sort the prefixGcd array in non-decreasing order (from smallest to largest).

Step 3: Form pairs.

Pair up the elements using the following rule:

Take the smallest unpaired element and the largest unpaired element to form a pair.
Repeat this process, each time choosing the smallest and largest from the remaining unpaired elements.
Continue until no more pairs can be formed.
If n is odd, the middle element in the sorted prefixGcd array stays unpaired and is simply ignored.

Step 4: Compute the answer.

For each formed pair, compute the gcd of its two elements. Return the sum of these GCD values across all formed pairs.

The term gcd(a, b) denotes the greatest common divisor of a and b.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Follows the three prescribed steps: build prefixGcd array, sort, then pair smallest-with-largest using two pointers and sum GCDs.

Open in Flowchart

Intuition

The key observation is that this problem doesn't require any clever trick or optimization — it can be solved by directly simulating the steps described in the problem statement.

Let's think about each step and how to handle it efficiently.

For building the prefixGcd array, notice that mxᵢ is just a running maximum. As we move through nums from left to right, the maximum can only stay the same or grow. So instead of recomputing the maximum from scratch at each index, we keep a single variable mx and update it with mx = max(mx, nums[i]) as we go. This lets us compute every prefixGcd[i] = gcd(nums[i], mx) in one pass.

After sorting prefixGcd in non-decreasing order, the pairing rule (smallest with largest) becomes a classic two-pointer pattern. The smallest unpaired element is at index i from the front, and the largest unpaired element is at index n - 1 - i from the back. So the i-th pair is (prefixGcd[i], prefixGcd[-i - 1]).

We only need to form n // 2 pairs:

When n is even, this exactly covers all elements.
When n is odd, the loop naturally stops before reaching the middle element, which means the middle element is automatically ignored — exactly as the problem requires.

Putting it together, we compute the gcd of each pair (prefixGcd[i], prefixGcd[-i - 1]) for i from 0 to n // 2 - 1, and sum these values to get the final answer.

Pattern Learn more about Math and Two Pointers patterns.

Solution Approach

Solution 1: Simulation

We solve this problem by directly simulating the steps described, using a single pass to build the array, sorting, and a two-pointer technique to form the pairs.

Step 1: Build the prefixGcd array in one pass.

We create an array prefixGcd of length n to store the value for each index i. We also maintain a variable mx to track the current maximum value seen so far, initialized to 0.

We iterate through nums. For each element x at index i:

Update the running maximum: mx = max(mx, x).
Compute the value: prefixGcd[i] = gcd(x, mx).

This avoids recomputing the maximum from scratch at every index and keeps the construction in O(n) time.

Step 2: Sort prefixGcd.

We sort prefixGcd in non-decreasing order with prefixGcd.sort(). This arranges the elements so that the smallest values are at the front and the largest at the back, which makes the pairing rule easy to apply.

Step 3: Form pairs with two pointers and sum the GCDs.

With the array sorted, the i-th pair consists of the i-th smallest element prefixGcd[i] and the i-th largest element prefixGcd[-i - 1]. We loop i from 0 to n // 2 - 1, compute gcd(prefixGcd[i], prefixGcd[-i - 1]) for each pair, and accumulate the results:

return sum(gcd(prefix_gcd[i], prefix_gcd[-i - 1]) for i in range(n // 2))

Using n // 2 as the loop bound handles both cases automatically: when n is even, all elements are paired; when n is odd, the middle element is naturally skipped and ignored.

Complexity Analysis:

Time complexity: O(n × log n + n × log M), where n is the length of nums and M is the maximum value in nums. The sorting step takes O(n × log n), and each gcd computation takes O(log M).
Space complexity: O(n) for the prefixGcd array (ignoring the space used by sorting).

Example Walkthrough

Let's trace through the solution using a small example: nums = [4, 6, 3, 8], so n = 4.

Step 1: Build the prefixGcd array in one pass.

We start with mx = 0 and walk through nums from left to right, updating the running maximum and computing the GCD at each index.

`i`	`nums[i]`	`mx = max(mx, nums[i])`	`prefixGcd[i] = gcd(nums[i], mx)`
0	4	`max(0, 4) = 4`	`gcd(4, 4) = 4`
1	6	`max(4, 6) = 6`	`gcd(6, 6) = 6`
2	3	`max(6, 3) = 6`	`gcd(3, 6) = 3`
3	8	`max(6, 8) = 8`	`gcd(8, 8) = 8`

After this single pass, prefixGcd = [4, 6, 3, 8].

Step 2: Sort prefixGcd.

Sorting in non-decreasing order:

prefixGcd = [3, 4, 6, 8]

Now the smallest values sit at the front and the largest at the back, ready for two-pointer pairing.

Step 3: Form pairs with two pointers and sum the GCDs.

Since n = 4, we loop i from 0 to n // 2 - 1 = 1, forming 2 pairs. The i-th pair is (prefixGcd[i], prefixGcd[-i - 1]).

`i`	front element `prefixGcd[i]`	back element `prefixGcd[-i - 1]`	pair	`gcd` of pair
0	`prefixGcd[0] = 3`	`prefixGcd[-1] = 8`	`(3, 8)`	`gcd(3, 8) = 1`
1	`prefixGcd[1] = 4`	`prefixGcd[-2] = 6`	`(4, 6)`	`gcd(4, 6) = 2`

Step 4: Compute the answer.

Summing the GCDs of all formed pairs:

1 + 2 = 3

The final answer is 3.

A note on the odd case: If we instead had nums = [4, 6, 3] giving a sorted prefixGcd = [3, 4, 6] with n = 3, the loop would run only for i in range(3 // 2) = range(1), forming the single pair (prefixGcd[0], prefixGcd[-1]) = (3, 6). The middle element 4 is never touched by the two pointers, so it is automatically ignored — exactly as the problem requires.

Solution Implementation

1from math import gcd
2from typing import List
3
4
5class Solution:
6    def gcdSum(self, nums: List[int]) -> int:
7        n = len(nums)
8
9        # transformed[i] = gcd(nums[i], max of nums[0..i])
10        transformed = [0] * n
11        running_max = 0
12        for i, x in enumerate(nums):
13            running_max = max(running_max, x)
14            transformed[i] = gcd(x, running_max)
15
16        # sort so we can pair the smallest values with the largest values
17        transformed.sort()
18
19        # pair transformed[i] (from the left) with transformed[-i - 1] (from the right)
20        # accumulate the gcd of each pair over the first half of the array
21        return sum(
22            gcd(transformed[i], transformed[-i - 1])
23            for i in range(n // 2)
24        )
25

1class Solution {
2    /**
3     * Computes a result based on the GCD relationships within the array.
4     *
5     * @param nums the input integer array
6     * @return the accumulated GCD sum as a long value
7     */
8    public long gcdSum(int[] nums) {
9        int n = nums.length;
10
11        // Stores the GCD of each element with the running maximum seen so far
12        int[] prefixGcd = new int[n];
13
14        // Tracks the maximum value encountered while iterating
15        int mx = 0;
16
17        // Build the prefixGcd array
18        for (int i = 0; i < n; i++) {
19            int x = nums[i];
20
21            // Update the running maximum
22            mx = Math.max(mx, x);
23
24            // Compute GCD of the current value and the running maximum
25            prefixGcd[i] = gcd(x, mx);
26        }
27
28        // Sort to enable pairing of smallest with largest elements
29        Arrays.sort(prefixGcd);
30
31        long ans = 0;
32
33        // Pair elements from both ends (two-pointer style) and sum their GCDs
34        for (int i = 0; i < n / 2; i++) {
35            ans += gcd(prefixGcd[i], prefixGcd[n - i - 1]);
36        }
37
38        return ans;
39    }
40
41    /**
42     * Computes the greatest common divisor of two integers
43     * using the iterative Euclidean algorithm.
44     *
45     * @param a the first integer
46     * @param b the second integer
47     * @return the greatest common divisor of a and b
48     */
49    private int gcd(int a, int b) {
50        while (b != 0) {
51            int t = a % b; // Remainder of a divided by b
52            a = b;         // Move b into a
53            b = t;         // Move the remainder into b
54        }
55        return a;
56    }
57}
58

1class Solution {
2public:
3    long long gcdSum(vector<int>& nums) {
4        int n = nums.size();
5
6        // prefixGcd[i] stores the gcd of nums[i] and the running maximum
7        // value seen so far (from index 0 up to i)
8        vector<int> prefixGcd(n);
9
10        int maxSoFar = 0; // tracks the maximum element encountered while iterating
11
12        for (int i = 0; i < n; i++) {
13            int current = nums[i];
14            maxSoFar = max(maxSoFar, current);   // update the running maximum
15            prefixGcd[i] = gcd(current, maxSoFar); // gcd of current element and running max
16        }
17
18        // Sort the computed gcd values in ascending order so that we can
19        // pair the smallest with the largest later
20        sort(prefixGcd.begin(), prefixGcd.end());
21
22        long long ans = 0;
23
24        // Pair elements from both ends (two-pointer style):
25        // smallest with largest, second smallest with second largest, etc.
26        // Accumulate the gcd of each pair into the answer.
27        for (int i = 0; i < n / 2; i++) {
28            ans += gcd(prefixGcd[i], prefixGcd[n - i - 1]);
29        }
30
31        return ans;
32    }
33};
34

1/**
2 * Computes a value based on the GCD pairing of a transformed array.
3 *
4 * Steps:
5 *  1. Build an auxiliary array where each element is the GCD of the current
6 *     number and the running maximum seen so far.
7 *  2. Sort that auxiliary array in ascending order.
8 *  3. Pair the smallest element with the largest, the second smallest with the
9 *     second largest, and so on, summing the GCD of each pair.
10 *
11 * @param nums - The input array of numbers.
12 * @returns The accumulated sum of GCDs over the symmetric pairs.
13 */
14function gcdSum(nums: number[]): number {
15    const length: number = nums.length;
16
17    // Stores gcd(nums[i], runningMax) for each index i.
18    const prefixGcd: number[] = new Array<number>(length);
19
20    // Tracks the maximum value encountered while iterating.
21    let runningMax = 0;
22
23    // First pass: fill prefixGcd using the running maximum.
24    for (let i = 0; i < length; i++) {
25        const current: number = nums[i];
26        runningMax = Math.max(runningMax, current);
27        prefixGcd[i] = gcd(current, runningMax);
28    }
29
30    // Sort ascending so we can pair the smallest with the largest.
31    prefixGcd.sort((a, b) => a - b);
32
33    // Accumulate the GCD of each symmetric pair (i, length - i - 1).
34    let answer = 0;
35    for (let i = 0; i < (length >> 1); i++) {
36        answer += gcd(prefixGcd[i], prefixGcd[length - i - 1]);
37    }
38
39    return answer;
40}
41
42/**
43 * Computes the greatest common divisor of two numbers using the
44 * iterative Euclidean algorithm.
45 *
46 * @param a - The first number.
47 * @param b - The second number.
48 * @returns The greatest common divisor of a and b.
49 */
50function gcd(a: number, b: number): number {
51    // Repeatedly replace (a, b) with (b, a % b) until b becomes 0.
52    while (b !== 0) {
53        const remainder: number = a % b;
54        a = b;
55        b = remainder;
56    }
57    return a;
58}
59

Time and Space Complexity

Time Complexity: O(n log M + n log n), where n is the length of the array and M is the maximum value in the array.
- The first loop iterates over all n elements. In each iteration, it computes gcd(x, mx), and each gcd call costs O(log M) time since the values are bounded by M. This contributes O(n log M).
- Sorting the prefix_gcd array takes O(n log n).
- The final summation loop runs n // 2 times, with each iteration performing a gcd operation costing O(log M), contributing O(n log M).
- Combining these terms gives O(n log M + n log n).
Space Complexity: O(n), where n is the length of the array.
- The prefix_gcd array stores n elements, requiring O(n) extra space. The sort operation may use additional space, but it remains within O(n). All other variables use constant space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misindexing the largest element when pairing

The most frequent mistake is getting the right-side index wrong when pairing the smallest element with the largest. Many people intuitively reach for transformed[n - i], but this is off by one and causes an IndexError (when i = 0, transformed[n] is out of bounds) or pairs the wrong elements.

Why it happens: When i = 0, the largest element is at index n - 1, not n. The correct expression is transformed[-i - 1] (equivalently transformed[n - 1 - i]).

Incorrect:

return sum(
    gcd(transformed[i], transformed[n - i])  # IndexError when i == 0
    for i in range(n // 2)
)

Correct:

return sum(
    gcd(transformed[i], transformed[-i - 1])  # or transformed[n - 1 - i]
    for i in range(n // 2)
)

Pitfall 2: Mishandling the odd-length middle element

When n is odd, the middle element must be skipped. A common error is looping range((n + 1) // 2) or range(n - n // 2), which over-counts and incorrectly pairs the middle element with itself, adding an extra gcd(mid, mid) = mid to the sum.

Why it happens: Confusion over how many pairs exist. There are exactly n // 2 pairs regardless of parity. Using n // 2 as the loop bound automatically skips the middle element for odd n.

Incorrect:

for i in range((n + 1) // 2):   # over-counts by one when n is odd
    total += gcd(transformed[i], transformed[-i - 1])

Correct:

for i in range(n // 2):         # exactly n//2 pairs; middle ignored for odd n
    total += gcd(transformed[i], transformed[-i - 1])

Pitfall 3: Recomputing the running maximum from scratch

A subtle inefficiency is recomputing max(nums[0..i]) inside the loop using a slice or nested loop instead of maintaining a running variable.

Why it matters: Slicing max(nums[:i + 1]) at every index turns Step 1 into an O(n²) operation, which can cause time-limit issues for large inputs. The running max should be updated incrementally in O(1) per step.

Inefficient:

for i, x in enumerate(nums):
    mx = max(nums[: i + 1])     # O(n) each iteration -> O(n^2) total
    transformed[i] = gcd(x, mx)

Efficient:

running_max = 0
for i, x in enumerate(nums):
    running_max = max(running_max, x)   # O(1) update
    transformed[i] = gcd(x, running_max)

Pitfall 4: Forgetting that `gcd(nums[i], mxᵢ)` is not always `nums[i]`

Since mxᵢ ≥ nums[i], it is tempting to assume gcd(nums[i], mxᵢ) = nums[i]. This is false in general — gcd(6, 8) = 2, not 6. The maximum being larger does not mean it is a multiple of the current element, so the gcd call cannot be skipped.

Solution: Always compute the actual gcd rather than shortcutting to nums[i]. Only when mxᵢ is a multiple of nums[i] (e.g., mxᵢ == nums[i]) does the result equal nums[i].

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know

3867. Sum of GCD of Formed Pairs

Problem Description

How We Pick the Algorithm

Why Simulation / Basic DSA?

Intuition

Solution Approach

Solution 1: Simulation

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Misindexing the largest element when pairing

Pitfall 2: Mishandling the odd-length middle element

Pitfall 3: Recomputing the running maximum from scratch

Pitfall 4: Forgetting that gcd(nums[i], mxᵢ) is not always nums[i]

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 4: Forgetting that `gcd(nums[i], mxᵢ)` is not always `nums[i]`