Skip to main content
Talentd

Maximum GCD-Sum of a Subarray - Solution & Explanation

HardPremiumFree on FleetCodeArrayMathBinary SearchNumber Theory6 min readAsked at: Thoughtworks
Practice this problem

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 s be the sum of all the elements of a.
  • Let g be the greatest common divisor of all the elements of a.
  • The gcd-sum of a is equal to s * 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.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 106
  • 1 <= 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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Incremental GCDO(n² log V)O(1)Small arrays or for understanding how subarray GCD evolves
Prefix Sum + GCD CompressionO(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

Video Solution

2941. Maximum GCD-Sum of a Subarray (Leetcode Hard) • Programming Live with Larry • 347 views views

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).

Ready to solve this problem?

Practice Maximum GCD-Sum of a Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays