Maximum GCD-Sum of a Subarray

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 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 themaximum gcd-sum of a subarray of nums with at least k elements.

Examples

Example 1:

1
2
3
4


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:

1
2
3
4


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^5
1 <= nums[i] <= 10^6
1 <= k <= n

Solution

Method 1 – GCD Enumeration with Prefix Sums

Intuition

The main idea is that for each possible GCD value, we can check all subarrays where every element is divisible by that GCD, and try to maximize the sum of such subarrays of length at least k. Since the GCD of a subarray must divide all its elements, we can enumerate all possible divisors for each element and use a sliding window to find the best sum for each divisor.

Approach

For each unique value in nums, enumerate all its divisors and map each divisor to the indices where it appears.
For each divisor d, collect all indices where nums[i] is divisible by d.
For each contiguous segment of such indices, use a sliding window of size at least k to find the maximum sum of a subarray where all elements are divisible by d.
For each such sum, compute gcd-sum as sum * d and keep track of the maximum.
Return the maximum gcd-sum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
public:
    int maxGcdSum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        unordered_map<int, vector<int>> divs;
        for (int i = 0; i < n; ++i) {
            for (int d = 1; d * d <= nums[i]; ++d) {
                if (nums[i] % d == 0) {
                    divs[d].push_back(i);
                    if (d != nums[i] / d) divs[nums[i]/d].push_back(i);
                }
            }
        }
        for (auto& [d, idxs] : divs) {
            int m = idxs.size();
            vector<long long> psum(m+1);
            for (int i = 0; i < m; ++i) psum[i+1] = psum[i] + nums[idxs[i]];
            for (int i = 0; i + k <= m; ++i) {
                ans = max(ans, (int)((psum[i+k] - psum[i]) * d));
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func maxGcdSum(nums []int, k int) int {
    n, ans := len(nums), 0
    divs := map[int][]int{}
    for i, v := range nums {
        for d := 1; d*d <= v; d++ {
            if v%d == 0 {
                divs[d] = append(divs[d], i)
                if d != v/d {
                    divs[v/d] = append(divs[v/d], i)
                }
            }
        }
    }
    for d, idxs := range divs {
        m := len(idxs)
        psum := make([]int, m+1)
        for i := 0; i < m; i++ {
            psum[i+1] = psum[i] + nums[idxs[i]]
        }
        for i := 0; i+k <= m; i++ {
            sum := psum[i+k] - psum[i]
            if sum*d > ans {
                ans = sum * d
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public int maxGcdSum(int[] nums, int k) {
        int n = nums.length, ans = 0;
        Map<Integer, List<Integer>> divs = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int d = 1; d * d <= nums[i]; ++d) {
                if (nums[i] % d == 0) {
                    divs.computeIfAbsent(d, z -> new ArrayList<>()).add(i);
                    if (d != nums[i] / d) divs.computeIfAbsent(nums[i]/d, z -> new ArrayList<>()).add(i);
                }
            }
        }
        for (var e : divs.entrySet()) {
            int d = e.getKey();
            List<Integer> idxs = e.getValue();
            int m = idxs.size();
            int[] psum = new int[m+1];
            for (int i = 0; i < m; ++i) psum[i+1] = psum[i] + nums[idxs.get(i)];
            for (int i = 0; i + k <= m; ++i) {
                ans = Math.max(ans, (psum[i+k] - psum[i]) * d);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    fun maxGcdSum(nums: IntArray, k: Int): Int {
        val n = nums.size
        var ans = 0
        val divs = mutableMapOf<Int, MutableList<Int>>()
        for (i in 0 until n) {
            var d = 1
            while (d * d <= nums[i]) {
                if (nums[i] % d == 0) {
                    divs.getOrPut(d) { mutableListOf() }.add(i)
                    if (d != nums[i] / d) divs.getOrPut(nums[i]/d) { mutableListOf() }.add(i)
                }
                d++
            }
        }
        for ((d, idxs) in divs) {
            val m = idxs.size
            val psum = IntArray(m+1)
            for (i in 0 until m) psum[i+1] = psum[i] + nums[idxs[i]]
            for (i in 0..m-k) {
                ans = maxOf(ans, (psum[i+k] - psum[i]) * d)
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def maxGcdSum(self, nums: list[int], k: int) -> int:
        from collections import defaultdict
        n = len(nums)
        ans = 0
        divs: dict[int, list[int]] = defaultdict(list)
        for i, v in enumerate(nums):
            d = 1
            while d * d <= v:
                if v % d == 0:
                    divs[d].append(i)
                    if d != v // d:
                        divs[v//d].append(i)
                d += 1
        for d, idxs in divs.items():
            m = len(idxs)
            psum = [0] * (m+1)
            for i in range(m):
                psum[i+1] = psum[i] + nums[idxs[i]]
            for i in range(m-k+1):
                ans = max(ans, (psum[i+k] - psum[i]) * d)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


impl Solution {
    pub fn max_gcd_sum(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let n = nums.len();
        let mut ans = 0;
        let mut divs: HashMap<i32, Vec<usize>> = HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            let mut d = 1;
            while d * d <= v {
                if v % d == 0 {
                    divs.entry(d).or_default().push(i);
                    if d != v / d {
                        divs.entry(v/d).or_default().push(i);
                    }
                }
                d += 1;
            }
        }
        for (d, idxs) in divs.iter() {
            let m = idxs.len();
            let mut psum = vec![0; m+1];
            for i in 0..m {
                psum[i+1] = psum[i] + nums[idxs[i]];
            }
            for i in 0..=m-k as usize {
                ans = ans.max((psum[i+k as usize] - psum[i]) * *d);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    maxGcdSum(nums: number[], k: number): number {
        const n = nums.length;
        let ans = 0;
        const divs: Record<number, number[]> = {};
        for (let i = 0; i < n; ++i) {
            for (let d = 1; d * d <= nums[i]; ++d) {
                if (nums[i] % d === 0) {
                    (divs[d] = divs[d] || []).push(i);
                    if (d !== nums[i] / d) (divs[nums[i]/d] = divs[nums[i]/d] || []).push(i);
                }
            }
        }
        for (const dStr in divs) {
            const d = Number(dStr);
            const idxs = divs[d];
            const m = idxs.length;
            const psum = new Array(m+1).fill(0);
            for (let i = 0; i < m; ++i) psum[i+1] = psum[i] + nums[idxs[i]];
            for (let i = 0; i + k <= m; ++i) {
                ans = Math.max(ans, (psum[i+k] - psum[i]) * d);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n * sqrt(maxA)), where n is the length of nums and maxA is the maximum value in nums. For each element, we enumerate its divisors (up to sqrt(maxA)), and for each divisor, we process its index list.
🧺 Space complexity: O(n * sqrt(maxA)), for storing the mapping from divisors to indices.

Problem#

Examples#

Solution#

Method 1 – GCD Enumeration with Prefix Sums#

Intuition#

Approach#

Code#

Complexity#