Is Sum of GCD of Formed Pairs easy or hard?

The problem is typically classified as Medium difficulty. The implementation is straightforward once you recognize the pairing pattern and apply efficient GCD computation.

Sum of GCD of Formed Pairs Python/Java solution

The implementation usually sorts the array and then iterates using two pointers to form pairs. Each step computes gcd(a, b) and accumulates the result. The same logic works in Python, Java, C++, Go, and TypeScript.

How to solve Sum of GCD of Formed Pairs in O(n)?

Pure O(n) time is generally not achievable because sorting is required to ensure pairs are formed in the correct order. After sorting, the pairing step itself runs in O(n), but the total complexity remains O(n log n).

What is the best approach for Sum of GCD of Formed Pairs?

The most practical solution uses simulation after sorting the array. Once sorted, use two pointers to form pairs from opposite ends and compute the GCD using the Euclidean algorithm. This approach runs in O(n log n + n logV) time and O(1) extra space.

Is Sum of GCD of Formed Pairs asked at Google/Amazon/Meta?

Problems involving GCD computation, array pairing, and number theory patterns frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of pair‑based GCD calculations are common in coding rounds.

What data structure is used in Sum of GCD of Formed Pairs?

The problem primarily uses arrays along with a two‑pointer traversal technique. The main algorithmic component is the Euclidean algorithm for computing the greatest common divisor.

What is the time complexity of Sum of GCD of Formed Pairs?

The optimized simulation approach takes O(n log n + n logV) time. Sorting the array requires O(n log n), and computing the GCD for each pair takes O(logV), where V is the maximum value in the array.

Description Hints 4 Solution Video 7:14

3867. Sum of GCD of Formed Pairs

Medium75.1% acceptance1 company

You are given an integer array nums of length n.

Construct an array prefixGcd where for each index i:

Let mx_i = max(nums[0], nums[1], ..., nums[i]).
prefixGcd[i] = gcd(nums[i], mx_i).

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]`	`mx_i`	`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]`	`mx_i`	`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 <= 10⁵
1 <= nums[i] <= 10⁹

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Maintain a running prefix maximum mx_i while iterating nums to compute prefixGcd[i] = gcd(nums[i], mx_i).

Hint 2

Sort prefixGcd in non-decreasing order.

Hint 3

Form pairs by combining smallest unpaired and largest unpaired elements.

Hint 4

Compute gcd for each pair and sum them; ignore middle element if n is odd.

7:14

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def gcdSum(self, nums: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,6,4]

Input

[3,6,2,8]

Your code is saved on this device.Solution