We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum GCD-Sum of a Subarray

Number: 3232

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an array of integers nums and an integer k, find the maximum gcd-sum of any contiguous subarray of nums with at least k elements. The gcd-sum of an array a is defined as (sum of all elements in a) multiplied by (greatest common divisor of all elements in a).

Key Insights

  • The gcd-sum depends on both the sum of elements and their GCD.
  • Brute forcing all subarrays is infeasible due to the constraint n ≤ 10^5.
  • Instead of iterating over all subarrays, we can iterate potential candidate GCD values.
  • For each candidate divisor d, check if there exists a contiguous segment of length at least k such that every element is divisible by d.
  • Use a sliding-window or two-pointer technique to quickly sum segments where each element is divisible by the candidate value.
  • Multiply the segment’s sum by the candidate divisor to evaluate candidate gcd-sum and track the maximum.

Space and Time Complexity

Time Complexity: Approximately O(max(nums) * n) in the worst-case scenario though practical performance may be better depending on the input distribution. Space Complexity: O(n) for auxiliary arrays used in the sliding window technique.

Solution

The solution iterates through potential divisors (from the maximum element down to 1). For each divisor d, we form a boolean array marking each element as valid if it is divisible by d. Using a sliding window approach, we then scan this boolean array along with the original array to find the maximum subarray sum where every element is valid and the subarray length is at least k. Multiplying this sum by d gives the candidate gcd-sum. The maximum candidate across all divisors is the answer.

Code Solutions

# Python solution for Maximum GCD-Sum of a Subarray

def max_gcd_sum(nums, k):
    # Helper function to find maximum subarray sum for valid segments
    def max_subarray_sum(valid, nums, k):
        max_sum = 0
        current_sum = 0
        count = 0
        for i in range(len(nums)):
            if valid[i]:
                current_sum += nums[i]
                count += 1
            else:
                # Reset the current window if an invalid element is encountered
                current_sum = 0
                count = 0
            if count >= k:
                max_sum = max(max_sum, current_sum)
        return max_sum

    max_val = max(nums)
    result = 0
    # Iterate candidate divisors from max value down to 1.
    for d in range(max_val, 0, -1):
        valid = [(num % d == 0) for num in nums]
        candidate_sum = max_subarray_sum(valid, nums, k)
        if candidate_sum > 0:
            result = max(result, candidate_sum * d)
    return result

# Example usage:
print(max_gcd_sum([2,1,4,4,4,2], 2))  # Expected output: 48
← Back to All Questions