Tap here to switch tabs
Problem
Submissions

Problem: Sum of GCD of Formed Pairs

Sum of GCD of Formed Pairs computes the GCD of each number and its prefix maximum, sorts those values, then sums GCDs of opposite-end pairs, leaving the middle unpaired if needed.

Statement

You are given an integer array nums of length n.

Construct an array prefixGcd of size n, where prefixGcd[i] is the greatest common divisor (gcd⁡\gcd) of nums[i] and the maximum value in nums from index 00 to index ii.

Sort prefixGcd in non decreasing order. Then, form pairs by pairing the jthj^{ {th}} element from the start with the jthj^{ {th}} element from the end, for all 0≤j<⌊n/2⌋0 \le j < \lfloor n / 2 \rfloor. If nn is odd, the middle element is left unpaired.

Return the sum of the greatest common divisor of each formed pair.

Constraints:

  • 1≤n==1 \le n == nums.length ≤105\le 10^5

  • 1≤1 \le nums[i] ≤109\le 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Sum of GCD of Formed Pairs

Sum of GCD of Formed Pairs computes the GCD of each number and its prefix maximum, sorts those values, then sums GCDs of opposite-end pairs, leaving the middle unpaired if needed.

Statement

You are given an integer array nums of length n.

Construct an array prefixGcd of size n, where prefixGcd[i] is the greatest common divisor (gcd⁡\gcd) of nums[i] and the maximum value in nums from index 00 to index ii.

Sort prefixGcd in non decreasing order. Then, form pairs by pairing the jthj^{ {th}} element from the start with the jthj^{ {th}} element from the end, for all 0≤j<⌊n/2⌋0 \le j < \lfloor n / 2 \rfloor. If nn is odd, the middle element is left unpaired.

Return the sum of the greatest common divisor of each formed pair.

Constraints:

  • 1≤n==1 \le n == nums.length ≤105\le 10^5

  • 1≤1 \le nums[i] ≤109\le 10^9