Sum of GCD of Formed Pairs solution and explanation
9 more videos on this problem
3867. Sum of GCD of Formed Pairs | Biweekly Contest 178 | LeetcodeRapid Syntax · 7:14 · 746 views
3867. Sum of GCD of Formed Pairs | Leetcode Daily - PythonLeetcode Daily · 5:27 · 524 views
Sum of GCD of Formed Pairs | LeetCode 3867 - Pythonimpoldev · 4:37 · 332 views
Daily Leetcode #2298: Jul 16, 2026 - 3867. Sum of GCD of Formed PairsProgramming Live with Larry · 6:23 · 276 views
Sum of GCD of Formed Pairs | LeetCode 3867 | Java Code | Developer CoderDeveloper Coder · 10:33 · 250 views
3867. Sum of GCD of Formed Pairs | LeetCode Java | Easy ExplanationExplainedbychhavi · 7:39 · 177 views
3867. Sum of GCD of Formed Pairs | POTD 16 July 2026 | C++ | LeetcodeTechie On Track · 7:23 · 111 views
Sum of GCD of Formed Pairs | Leetcode 3867 | Explanation With Code | Javacodewithsitaram · 14:07 · 106 views
Sum of GCD of formed pairs | Leetcode biweekly contest | 3867.Prince Gupta Study · 21:01 · 80 views
LeetCode Problem 3867 | Sum of GCD of Formed PairsRepovive TV · 6:24 · 66 views
The problem
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
prefixGcdin 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
gcdof the two elements. - If
nis odd, the middle element in theprefixGcdarray remains unpaired and should be ignored.
Return an integer denoting the sum of the GCD values of all formed pairs.
The termgcd(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 <= 1051 <= nums[i] <= 109
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.
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))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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n^2 * logV) | O(1) | Useful for understanding the problem or validating small inputs |
| Simulation with Sorting + Two Pointers | O(n log n + n logV) | O(1) | Preferred approach for interviews and large inputs |
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.