Skip to main content
Talentd

Sum of GCD of Formed Pairs - Solution & Explanation

MediumArrayMathTwo PointersSimulation8 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array of integers and must form pairs according to the problem’s rules, then compute the sum of the gcd(a, b) for every pair created. The core task is pairing elements in the correct order and efficiently calculating the greatest common divisor for each pair.

Approach 1: Brute Force Pair Enumeration (O(n^2 * logV) time, O(1) space)

The most direct idea is to try every possible pair of elements and compute the GCD for each combination. For an array of size n, this requires iterating through all i, j pairs where i < j and calling the Euclidean algorithm to compute gcd(nums[i], nums[j]). The time complexity becomes O(n^2 * logV), where V is the maximum value in the array. This approach is mainly useful for understanding the problem and verifying small test cases, but it quickly becomes impractical for larger inputs.

Approach 2: Simulation with Sorting and Two Pointers (O(n log n + n logV) time, O(1) space)

A more practical approach simulates the pair formation process directly. First sort the array so the pairing order becomes deterministic. Then use a two‑pointer strategy: one pointer starts from the beginning and another from the end. At each step, form a pair using the elements pointed to by the two pointers and compute their gcd using the Euclidean algorithm. Add this value to the running sum, then move the pointers inward.

This works because sorting ensures elements are paired in the intended order while avoiding repeated scanning. Each element participates in exactly one pairing step, so the simulation runs in linear time after sorting. The GCD computation itself takes O(logV), making the overall complexity O(n log n + n logV). The approach relies on concepts from Array, Two Pointers, and Number Theory.

Recommended for interviews: Interviewers expect the simulation approach combined with efficient gcd computation. Starting with the brute force idea shows you understand the pairing requirement, but transitioning to sorting plus two pointers demonstrates the ability to optimize time complexity while keeping the implementation simple.

Solution

We simulate according to the problem description.

We create an array 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 prefixGcd[i]. Then we sort 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair EnumerationO(n^2 * logV)O(1)Useful for understanding the problem or validating small inputs
Simulation with Sorting + Two PointersO(n log n + n logV)O(1)Preferred approach for interviews and large inputs

Video Solution

3867. Sum of GCD of Formed Pairs | Biweekly Contest 178 | Leetcode • Rapid Syntax • 746 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sum of GCD of Formed Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays