Problem Description

You are given an array of integers nums and an integer k.

For any array a, the gcd-sum is calculated by:

1. Finding the sum s of all elements in a
2. Finding the greatest common divisor g of all elements in a
3. Computing the gcd-sum as s * g

Your task is to find the maximum gcd-sum among all possible subarrays of nums that contain at least k elements.

For example, if you have a subarray [6, 9, 12] with k = 2:

• Sum s = 6 + 9 + 12 = 27
• GCD g = gcd(6, 9, 12) = 3
• gcd-sum = 27 * 3 = 81

You need to check all valid subarrays (those with length ≥ k) and return the maximum gcd-sum found.

The solution uses a sliding window approach combined with GCD tracking. It maintains a list f that stores pairs of (starting_index, gcd_value) for all subarrays ending at the current position. For each position i, it:

• Updates the GCD values for all previous subarrays by including nums[i]
• Removes duplicate GCD values to optimize performance
• Checks all subarrays ending at position i with length ≥ k and updates the maximum gcd-sum

The prefix sum array s is used to quickly calculate subarray sums, where s[i+1] - s[j] gives the sum of elements from index j to i.

Intuition

The key observation is that as we extend a subarray by adding more elements, the GCD can only stay the same or decrease (it never increases). This is because the GCD of a set of numbers is always less than or equal to the GCD of any subset.

Consider what happens when we fix the ending position of subarrays. For all subarrays ending at position i, we need to track their GCDs. However, there's an important property: the number of distinct GCD values for all subarrays ending at a fixed position is limited.

Why? Because each time we extend a subarray to the left (making it longer), the GCD either stays the same or becomes a divisor of the previous GCD. Since a number has a limited number of divisors (at most O(log n)), we won't have too many distinct GCD values.

This leads us to the approach: for each ending position i, we maintain a list of (starting_position, gcd_value) pairs. But we only keep one representative for each distinct GCD value - specifically, the rightmost starting position that gives that GCD. This is optimal because a shorter subarray with the same GCD will always have a smaller or equal sum compared to a longer one.

As we move to the next position i+1, we update all existing GCDs by computing gcd(existing_gcd, nums[i+1]). If multiple subarrays now have the same GCD after this update, we only keep the shortest one (rightmost starting position).

The prefix sum array allows us to calculate any subarray sum in O(1) time. For each valid subarray (length ≥ k), we compute its gcd-sum and track the maximum.

This approach efficiently explores all possible subarrays while avoiding redundant calculations by leveraging the monotonic property of GCD values.

Learn more about Math and Binary Search patterns.

Solution Approach

The implementation uses a sliding window technique with GCD tracking. Let's walk through the algorithm step by step:

1. Initialize Prefix Sum Array:

s = list(accumulate(nums, initial=0))

We create a prefix sum array where s[i] represents the sum of elements from index 0 to i-1. This allows us to calculate any subarray sum in O(1) time using s[right+1] - s[left].

2. Main Loop - Process Each Ending Position: For each position i in the array, we treat it as the ending position of potential subarrays:

for i, v in enumerate(nums):

3. Update GCD Values for Existing Subarrays:

g = []
for j, x in f:
    y = gcd(x, v)
    if not g or g[-1][1] != y:
        g.append((j, y))

• For each subarray (j, x) in our list f (where j is starting index and x is GCD), we compute the new GCD when including nums[i]
• We only add (j, y) to the new list g if this GCD value y is different from the last one we added
• This deduplication is crucial: if multiple subarrays have the same GCD, we keep only the one with the largest starting index (shortest subarray)

4. Add Current Element as New Subarray:

f = g
f.append((i, v))

After updating existing subarrays, we add a new subarray starting and ending at position i with GCD = nums[i].

5. Calculate Maximum GCD-Sum:

for j, x in f:
    if i - j + 1 >= k:
        ans = max(ans, (s[i + 1] - s[j]) * x)

For each subarray ending at position i:

• Check if its length (i - j + 1) is at least k
• If valid, calculate its gcd-sum: sum * gcd = (s[i+1] - s[j]) * x
• Update the maximum answer

Time Complexity: O(n² × log(max_value)) where n is the array length. The log factor comes from GCD computation.

Space Complexity: O(n) for storing the prefix sums and the list of (index, gcd) pairs.

The algorithm efficiently handles the problem by maintaining only distinct GCD values for each ending position, avoiding redundant calculations while ensuring we find the maximum gcd-sum.

Example Walkthrough

Let's walk through the algorithm with nums = [6, 3, 9] and k = 2.

Initial Setup:

• Prefix sum array: s = [0, 6, 9, 18]
• Answer: ans = 0
• GCD tracking list: f = []

Iteration 1 (i=0, v=6):

• Update existing subarrays: f is empty, so g = []
• Add new subarray starting at index 0: f = [(0, 6)]
• Check valid subarrays (length ≥ 2): None yet (current length is 1)
• ans = 0

Iteration 2 (i=1, v=3):

• Update existing subarrays:
  • For (0, 6): new GCD = gcd(6, 3) = 3
  • g = [(0, 3)]
• Add new subarray starting at index 1: f = [(0, 3), (1, 3)]
• Check valid subarrays:
  • Subarray [0,1]: length = 2 ≥ k
    • Sum = s[2] - s[0] = 9 - 0 = 9
    • GCD = 3
    • gcd-sum = 9 × 3 = 27
  • Subarray [1,1]: length = 1 < k (skip)
• ans = 27

Iteration 3 (i=2, v=9):

• Update existing subarrays:
  • For (0, 3): new GCD = gcd(3, 9) = 3
  • For (1, 3): new GCD = gcd(3, 9) = 3
  • Since both have GCD = 3, keep only the rightmost: g = [(1, 3)]
• Add new subarray starting at index 2: f = [(1, 3), (2, 9)]
• Check valid subarrays:
  • Subarray [1,2]: length = 2 ≥ k
    • Sum = s[3] - s[1] = 18 - 6 = 12
    • GCD = 3
    • gcd-sum = 12 × 3 = 36
  • Subarray [2,2]: length = 1 < k (skip)
• ans = max(27, 36) = 36

Final Result: The maximum gcd-sum is 36 from subarray [3, 9].

Note how the algorithm efficiently handled duplicate GCD values in iteration 3. Both subarrays [6,3,9] and [3,9] have GCD = 3, but we only kept the shorter one [3,9] since it would have a smaller sum. This optimization reduces redundant calculations while ensuring we find the maximum gcd-sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × log(max(nums)))

The algorithm iterates through each element in nums (n iterations). For each element at position i:

• It processes the list f which can contain at most O(n) entries in the worst case
• For each entry in f, it computes the GCD with the current element, which takes O(log(max(nums))) time
• The deduplication step ensures that f contains at most O(log(max(nums))) distinct GCD values after processing, as the GCD can only decrease and has at most O(log(max(nums))) distinct divisors
• However, in the worst case scenario before deduplication, we process up to i elements

Therefore, the total time complexity is O(n × n × log(max(nums))) = O(n² × log(max(nums))).

Space Complexity: O(n)

The space usage consists of:

• The prefix sum array s which uses O(n) space
• The list f which stores at most O(min(n, log(max(nums)))) entries after deduplication, but this is bounded by O(n)
• The temporary list g which also uses at most O(n) space during construction
• Other variables use O(1) space

The dominant space usage is O(n) from the prefix sum array and the working lists.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling GCD Deduplication Correctly

The Pitfall: A common mistake is either forgetting to deduplicate GCD values or implementing it incorrectly. Without deduplication, the algorithm stores redundant segments with the same GCD value, leading to:

• Exponential growth in the number of segments stored
• Time Limit Exceeded (TLE) for large inputs
• Unnecessary repeated calculations

Incorrect Implementation:

# WRONG: Storing all segments without deduplication
for start_index, prev_gcd in gcd_segments:
    new_gcd = gcd(prev_gcd, current_value)
    new_gcd_segments.append((start_index, new_gcd))  # Always appending

Why This Fails: Consider the array [12, 12, 12, 12, 12]. Without deduplication:

• Position 0: segments = [(0, 12)]
• Position 1: segments = [(0, 12), (1, 12)]
• Position 2: segments = [(0, 12), (1, 12), (2, 12)]
• Position 3: segments = [(0, 12), (1, 12), (2, 12), (3, 12)]
• Position 4: segments = [(0, 12), (1, 12), (2, 12), (3, 12), (4, 12)]

All these segments have the same GCD (12), but we're storing them all unnecessarily.

Correct Solution:

for start_index, prev_gcd in gcd_segments:
    new_gcd = gcd(prev_gcd, current_value)
    # Only append if this GCD is different from the last one added
    if not new_gcd_segments or new_gcd_segments[-1][1] != new_gcd:
        new_gcd_segments.append((start_index, new_gcd))

2. Incorrect Prefix Sum Usage

The Pitfall: Misunderstanding how prefix sums work, especially with the initial=0 parameter, leading to off-by-one errors.

Incorrect Implementation:

# WRONG: Incorrect indexing
prefix_sums = list(accumulate(nums))  # No initial=0
subarray_sum = prefix_sums[current_index] - prefix_sums[start_index]

Why This Fails: Without initial=0, prefix_sums[i] contains the sum up to and including nums[i]. This makes it impossible to calculate the sum starting from index 0 correctly.

Correct Solution:

# With initial=0, prefix_sums[i] = sum of nums[0:i]
prefix_sums = list(accumulate(nums, initial=0))
# Sum from start_index to current_index (inclusive)
subarray_sum = prefix_sums[current_index + 1] - prefix_sums[start_index]

3. Forgetting to Add Single-Element Segments

The Pitfall: Only updating existing segments with the current element but forgetting to create a new segment starting at the current position.

Incorrect Implementation:

# WRONG: Missing the single-element segment
for start_index, prev_gcd in gcd_segments:
    new_gcd = gcd(prev_gcd, current_value)
    if not new_gcd_segments or new_gcd_segments[-1][1] != new_gcd:
        new_gcd_segments.append((start_index, new_gcd))
gcd_segments = new_gcd_segments
# Forgot to add: gcd_segments.append((current_index, current_value))

Why This Fails: This misses all subarrays that start at position current_index. For example, if k=1 and the maximum gcd-sum comes from a single element, this implementation would miss it entirely.

Correct Solution:

# After processing existing segments, add new segment for current position
gcd_segments = new_gcd_segments
gcd_segments.append((current_index, current_value))

4. Integer Overflow in Other Languages

The Pitfall: When implementing in languages like C++ or Java, the product subarray_sum * subarray_gcd might overflow 32-bit integers.

Example:

• Array with large values: [1000000, 1000000, ..., 1000000] (1000 elements)
• Sum = 10^9, GCD = 10^6
• Product = 10^15 (exceeds 32-bit integer range)

Solution: Use 64-bit integers (long long in C++, long in Java) for storing sums and products:

// C++ example
long long subarray_sum = prefix_sums[current_index + 1] - prefix_sums[start_index];
long long product = subarray_sum * (long long)subarray_gcd;