GCD Sum of Prescribed Derived-Value Pairs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given a positive integer array `nums`, construct a derived array `prefixGcd` using the original input order. At each index `i`:
```text
mx_i = max(nums[0],...,nums[i])
prefixGcd[i] = gcd(nums[i],mx_i)
```
Then sort `prefixGcd` in non-decreasing order. Repeatedly pair its smallest unpaired element with its largest unpaired element. Add the GCD of each pair. If an odd number of values leaves a middle element unpaired, ignore it.
Return that sum. Here GCD is the greatest common divisor of the two supplied positive integers.
```cpp
class Solution {
public:
long long gcdSum(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [8,12,6,9]
Output: 5
Explanation: Prefix maxima are [8,12,12,12], giving derived values [8,12,6,3]. Sorting gives [3,6,8,12]. The pair GCDs are gcd(3,12)=3 and gcd(6,8)=2, totaling 5.
```
**Example 2:**
```text
Input: nums = [7]
Output: 0
Explanation: The derived array contains only 7. It remains unpaired and contributes nothing.
```
### Constraints
- `1 <= nums.length <= 100000`.
- `1 <= nums[i] <= 1000000000`.
### Clarifying Questions
- Is `prefixGcd[i]` the GCD of the entire prefix? No; use exactly the two-argument formula above.
- Is the prefix maximum inclusive of `nums[i]`? Yes.
- Can the original array be reordered before the derived values are defined? No.
- Can a different pairing be chosen to optimize the sum? No; the sorted smallest/largest pairing is fixed.
- Does an unpaired middle element contribute its own value? No; it is ignored.
### What a Strong Answer Covers
- The exact inclusive-prefix-maximum formula in the original order.
- The specified ordering and pairing of derived values, including repetitions.
- Odd lengths, a singleton, and correct summation of pair GCDs.
- A completeness proof, numeric safety, and full-input resource bounds.
### Follow-up Questions
- What extra output would be needed to report the formed pairs?
- How would allowing a freely chosen pairing change the requested task?
```hint Implement the two stages without mixing their orders
Maintain the running maximum while deriving each GCD from the original sequence. Sort only the completed derived array. Pair indices from its two ends until they meet, accumulating into a wide integer.
```
Overview: Sum GCDs of prescribed pairs formed from prefix-maximum-derived values. Covers original order, odd lengths, wide sums, proof, and C++ code.
