Maximum GCD-Sum of a Subarray solution and explanation
The problem
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.
Solution
class Solution:
def maxGcdSum(self, nums: List[int], k: int) -> int:
s = list(accumulate(nums, initial=0))
f = []
ans = 0
for i, v in enumerate(nums):
g = []
for j, x in f:
y = gcd(x, v)
if not g or g[-1][1] != y:
g.append((j, y))
f = g
f.append((i, v))
for j, x in f:
if i - j + 1 >= k:
ans = max(ans, (s[i + 1] - s[j]) * x)
return ansclass Solution {
public long maxGcdSum(int[] nums, int k) {
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
List<int[]> f = new ArrayList<>();
long ans = 0;
for (int i = 0; i < n; ++i) {
List<int[]> g = new ArrayList<>();
for (var e : f) {
int j = e[0], x = e[1];
int y = gcd(x, nums[i]);
if (g.isEmpty() || g.get(g.size() - 1)[1] != y) {
g.add(new int[] {j, y});
}
}
f = g;
f.add(new int[] {i, nums[i]});
for (var e : f) {
int j = e[0], x = e[1];
if (i - j + 1 >= k) {
ans = Math.max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}class Solution {
public:
long long maxGcdSum(vector<int>& nums, int k) {
int n = nums.size();
long long s[n + 1];
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
vector<pair<int, int>> f;
long long ans = 0;
for (int i = 0; i < n; ++i) {
vector<pair<int, int>> g;
for (auto [j, x] : f) {
int y = gcd(x, nums[i]);
if (g.empt() || g.back().second != y) {
g.emplace_back(j, y);
}
}
f = move(g);
f.emplace_back(i, nums[i]);
for (auto [j, x] : f) {
if (i - j + 1 >= k) {
ans = max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
};function maxGcdSum(nums: number[], k: number): number {
const n: number = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
}
let f: [number, number][] = [];
let ans: number = 0;
for (let i = 0; i < n; ++i) {
const g: [number, number][] = [];
for (const [j, x] of f) {
const y: number = gcd(x, nums[i]);
if (g.length === 0 || g.at(-1)[1] !== y) {
g.push([j, y]);
}
}
f = g;
f.push([i, nums[i]]);
for (const [j, x] of f) {
if (i - j + 1 >= k) {
ans = Math.max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func maxGcdSum(nums []int, k int) int64 {
n := len(nums)
s := make([]int64, n+1)
s[0] = 0
for i, x := range nums {
s[i+1] = s[i] + int64(x)
}
type pair [2]int
var f []pair
var ans int64
for i := 0; i < n; i++ {
var g []pair
for _, p := range f {
j, x := p[0], p[1]
y := int(gcd(int(x), nums[i]))
if len(g) == 0 || g[len(g)-1][1] != y {
g = append(g, pair{j, y})
}
}
f = g
f = append(f, pair{i, nums[i]})
for _, p := range f {
j, x := p[0], p[1]
if i-j+1 >= k {
ans = max(ans, (s[i+1]-s[j])*int64(x))
}
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}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 |
Frequently asked questions
Is Maximum GCD-Sum of a Subarray easy or hard?
Maximum GCD-Sum of a Subarray is considered a Hard problem. The difficulty comes from combining multiple concepts: subarray enumeration, efficient GCD updates, and prefix sums. Recognizing that subarray GCD values collapse into a small set is the key insight.
Maximum GCD-Sum of a Subarray Python/Java solution
Python, Java, C++, Go, and TypeScript implementations all follow the same pattern: compute prefix sums, maintain a list of current GCD states, update them using gcd(prev, nums[i]), merge duplicates, and evaluate gcd * subarray sum. The complexity remains O(n log V) regardless of language.
How to solve Maximum GCD-Sum of a Subarray in O(n)?
Strict O(n) is difficult because every extension of a subarray requires a GCD operation. The closest practical complexity is O(n log V) using GCD compression. By merging identical GCD states for subarrays ending at each index, the algorithm keeps only a small number of candidates and processes the array nearly linearly.
What is the best approach for Maximum GCD-Sum of a Subarray?
The most efficient approach uses prefix sums combined with GCD compression. For every index, track all distinct GCD values of subarrays ending at that position and merge duplicates. This limits the number of states to about O(log V). The overall complexity becomes O(n log V), which works well for large arrays.
Is Maximum GCD-Sum of a Subarray asked at Google/Amazon/Meta?
Problems involving subarray GCDs and prefix sums appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the technique of maintaining compressed GCD states for subarrays is a known interview pattern in number theory and array optimization questions.
What data structure is used in Maximum GCD-Sum of a Subarray?
The solution typically uses arrays or lists to store compressed GCD states and a prefix sum array for fast range sum queries. Each state represents a pair of (gcd value, start index). These states are updated iteratively while scanning the array.
What is the time complexity of Maximum GCD-Sum of a Subarray?
The optimal solution runs in O(n log V) time, where n is the array length and V is the maximum value in the array. Each index generates a small set of distinct GCD states and each update requires a gcd computation that costs O(log V). Space complexity is typically O(log V).