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

Description Hints 5 Solution Video 1:46:32

2941. Maximum GCD-Sum of a Subarray

Hard39.9% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n

Asked at 1 company

Thoughtworks

Topics

Hints open one at a time

Hint 1

Try to answer the query of asking GCD of a subarray in O(1) using sparse tables and preprocessing.

Hint 2

For every index L, let’s find the subarray starting at the index L and maximizing gcd-sum.

Hint 3

Use the fact that if L is fixed, then by adding one more element to the end of a subarray, two things can happen: the gcd remains the same as the last gcd or becomes at least half of the last one.

Hint 4

Now we can use binary search to find the last index R such that gcd of the elements of nums[L..R] would be equal to nums[L].

Hint 5

Now add nums[R + 1] to the current subarray and continue the process to find the last index that has the same gcd as the current gcd of elements.

1:46:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,1,4,4,4,2]
2

Input

[7,3,9,4]
1

Your code is saved on this device.Solution