Sum of GCD of Formed Pairs - Video Solutions
3867. Sum of GCD of Formed Pairs | Biweekly Contest 178 | Leetcode
Sum of GCD of Formed Pairs - Video Solution
Watch 10 video solutions for Sum of GCD of Formed Pairs, a medium level problem involving Array, Math, Two Pointers. This walkthrough by Rapid Syntax has 746 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
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] <= 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.
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 |