Maximum GCD-Sum of a Subarray - Video Solutions
2941. Maximum GCD-Sum of a Subarray (Leetcode Hard)
Maximum GCD-Sum of a Subarray - Video Solution
Watch the video solution for Maximum GCD-Sum of a Subarray, a hard level problem involving Array, Math, Binary Search. This walkthrough by Programming Live with Larry has 347 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an array of integers nums and an integer k.
The gcd-sum of an array a is calculated as follows:
- Let
sbe the sum of all the elements ofa. - Let
gbe the greatest common divisor of all the elements ofa. - The gcd-sum of
ais equal tos * g.
Return the maximum gcd-sum of a subarray of nums with at least k elements.
Example 1:
Input: nums = [2,1,4,4,4,2], k = 2 Output: 48 Explanation: We take the subarray [4,4,4], the gcd-sum of this array is 4 * (4 + 4 + 4) = 48. It can be shown that we can not select any other subarray with a gcd-sum greater than 48.
Example 2:
Input: nums = [7,3,9,4], k = 1 Output: 81 Explanation: We take the subarray [9], the gcd-sum of this array is 9 * 9 = 81. It can be shown that we can not select any other subarray with a gcd-sum greater than 81.
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= 1061 <= k <= n
Approach Overview
Problem Overview: You are given an integer array and need the maximum value of gcd(subarray) * sum(subarray) for any valid subarray. The challenge is computing GCDs across many ranges while still tracking subarray sums efficiently.
Approach 1: Brute Force with Incremental GCD (O(n² log V) time, O(1) space)
Start every subarray at index i and extend it one element at a time to the right. Maintain the running GCD as you expand the window using gcd(current_gcd, nums[j]). Track the running sum or compute it using prefix sums, then update the answer with gcd * sum. This approach checks all O(n²) subarrays and each GCD update costs O(log V), where V is the value range. It works for small inputs but quickly becomes too slow for large arrays.
Approach 2: GCD Compression + Prefix Sum (O(n log V) time, O(log V) space)
Instead of recomputing the GCD for every subarray independently, keep a compressed list of all distinct GCD values for subarrays ending at the current index. When you move to index r, extend every previous GCD segment by computing gcd(prev_gcd, nums[r]), and also start a new segment with nums[r]. Many segments collapse to the same GCD, so you merge them and keep the earliest starting index. This keeps the number of active GCD states small (typically O(log V)).
Use a prefix sum array to compute subarray sums in O(1). For each compressed state (g, start), calculate the subarray sum ending at r and update the candidate value g * sum. Because each index only produces a limited number of distinct GCD states, the total work across the array remains near linear.
This technique appears frequently in number theory problems involving subarray GCDs. Prefix sums provide constant-time range sums, a common pattern in array problems. Efficient GCD merging prevents the quadratic explosion that the brute-force method suffers from.
Recommended for interviews: The compressed GCD approach with prefix sums is what interviewers expect for a hard problem in math and number theory. Brute force shows you understand the definition of subarray GCDs, but the optimized method demonstrates algorithmic maturity by reusing previously computed GCD states and reducing the search space from quadratic to near linear.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Incremental GCD | O(n² log V) | O(1) | Small arrays or for understanding how subarray GCD evolves |
| Prefix Sum + GCD Compression | O(n log V) | O(log V) | General case and competitive programming constraints |
| Prefix Sum + Optimized GCD State Merging | ~O(n log V) | O(log V) | Large inputs where repeated GCD values must be merged aggressively |