2941. Maximum GCD-Sum of a Subarray

HardArrayMathBinary SearchNumber Theory
Leetcode Link

Problem Description

You are given an array of integers nums and an integer k. Your task is to find the maximum "gcd-sum" of any subarray of nums that has at least k elements. The "gcd-sum" of an array is calculated by summing all the elements of the array and then multiplying this sum by the greatest common divisor (GCD) of all the elements in the array. Formally, if s is the sum of the array and g is the GCD of the array, then the "gcd-sum" is s * g.

Intuition

The challenge is to find a subarray with a high sum s and also a high GCD g, as these two factors combined will give us a high "gcd-sum". A brute force approach to this problem would be to check every possible subarray of nums that has at least k elements, calculate the "gcd-sum" for each, and keep track of the maximum value. However, this would be too slow for large arrays since it would require examining a potentially exponential number of subarrays.

The more efficient approach implemented here involves a two-step process:

  1. Store the progressive sums of nums in an array s, where the sum of elements from the start to index i is in s[i+1]. This allows us to quickly calculate the sum of any subarray.

  2. Keep a list f of pairs (j, x), where j represents an index in nums and x represents the GCD of the subarray ending at index i that starts after index j. To maintain this list, we iterate over nums, and for each element v at index i, we update the list based on the GCD of v with the second elements of the existing pairs in f.

At each step, we calculate the "gcd-sum" for subarrays that include the current element v and compare this "gcd-sum" to our current maximum, storing the larger of the two. The elements v of nums are incorporated progressively, potentially forming subarrays with larger k and effectively tracking the maximum "gcd-sum" that fulfills the condition of having at least k elements.

Learn more about Math and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation of the solution leverages dynamic programming techniques and an understanding of mathematical properties of the greatest common divisor (GCD). Below are the key components of the algorithm, which explain how it works:

  1. Prefix Sums: The algorithm begins by computing a list of prefix sums s using Python's accumulate function with the initial=0 parameter. Prefix sums are a powerful tool in array processing that lets us compute the sum of any subrange of the array in constant time, once the prefix sum array is built.

  2. Dynamic GCD List (f): A list f is created to store pairs (j, x) where j is the beginning index of a subarray ending at the current index i, and x is the GCD of all the numbers between j and i. Initially, f is empty, and it's updated as we iterate through the array.

  3. Iterative GCD Updates: As the algorithm iterates through each element v in nums, it creates a new list g to hold the updated values of GCD pairs. For each element in f, the algorithm calculates the GCD with the current element v. If g is empty or the last GCD in g is different from the current GCD, the pair is added to g. After going through all pairs in f, f is replaced with the new list g.

  4. Subarray GCD-Sum Calculation: For each f pair (j, x), if the subarray from j to i (inclusive) has at least k elements, the algorithm computes the "gcd-sum" for that subarray using the formula (s[i + 1] - s[j]) * x, where s[i + 1] is the sum up to i (inclusive) from the prefix sums array s and x is the GCD for this subarray. The result is compared with the current maximum "gcd-sum" (ans) and updated if greater.

  5. Optimization: To optimize, pair (i, v) is also appended to f after the update loop, representing the subarray containing only the single element v starting and ending at i.

  6. Return Maximum gcd-sum: After iterating through each number in nums, the maximum "gcd-sum" found during the process (ans) is returned as the result.

In summary, the algorithm efficiently evaluates subarrays for their "gcd-sum" by maintaining a dynamic list of GCDs and using prefix sums to calculate subarray sums quickly. This solution deftly handles the computational complexity by avoiding redundant calculations and making use of the mathematical properties of GCD to only keep the necessary elements in the f list.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's say we have an array nums = [3, 6, 2, 8, 4] and we're trying to find the maximum "gcd-sum" of any subarray with at least k = 2 elements.

Following the steps of the solution approach:

  1. Prefix Sums: We calculate the prefix sums s array, which would look like [0, 3, 9, 11, 19, 23]. The array s indicates the progressive sums such that s[i] gives the sum of the first i-1 elements of nums.

  2. Dynamic GCD List (f): We initialize an empty list f to store pairs of beginning indices and GCDs of subarrays.

  3. Iterative GCD Updates: We iterate over nums.

    • When i = 0 (v = 3), f is still empty, so we initialize it with (0, 3), since a subarray starting and ending with 3 has a GCD of 3.
    • When i = 1 (v = 6), we calculate the GCD of each pair in f with 6, resulting in (0, 3). Since len(f) = 1, it remains unchanged. We then add (1, 6) to f, now holding [(0, 3), (1, 6)].
    • For i = 2 (v = 2), we update f to [(0, 1), (1, 2), (2, 2)] - each GCD is calculated with 2.
    • This continues until we've iterated through all elements of nums.

  4. Subarray GCD-Sum Calculation: For each pair (j, x) in f, we calculate the "gcd-sum" if it meets our subarray size condition. For example, for the pair (1, 6) when i = 4 (v = 4), the subarray [6, 2, 8, 4] has a sum of 20 (from s[5] - s[1]) and a GCD of 2 (not 6 due to earlier GCD update with 8 and 4). So the "gcd-sum" is 20 * 2 = 40. We compare this with the current maximum to possibly update it.

  5. Optimization: After the updates, we add the pair (i, v) for the single element subarray v.

  6. Return Maximum gcd-sum: Once we've iterated over every element, we find that the maximum "gcd-sum" is from the subarray [6, 2, 8, 4] which is 40. This would be the output of the algorithm.

This simple example illustrates the process for finding the maximum "gcd-sum" using the solution approach described.

Solution Implementation

1from itertools import accumulate
2from math import gcd
3from typing import List
4
5class Solution:
6    def maxGcdSum(self, nums: List[int], k: int) -> int:
7        # Create a prefix sum array where `s[i]` is the sum of the first `i` numbers
8        prefix_sum = list(accumulate(nums, initial=0))
9      
10        # Initialize an empty list `gcds` that will store pairs (index, gcd_value)
11        gcds = []
12      
13        # Initialize the answer variable to 0
14        max_sum = 0
15
16        # Iterate over the list of numbers with their indices
17        for i, num in enumerate(nums):
18            # Initialize a temporary list to store current gcd values
19            temp_gcds = []
20          
21            # Iterate over the list `gcds` and calculate gcd for each pair with the current number
22            for index, gcd_value in gcds:
23                current_gcd = gcd(gcd_value, num)
24              
25                # If the current gcd is different from the last one in temp_gcds, append it
26                if not temp_gcds or temp_gcds[-1][1] != current_gcd:
27                    temp_gcds.append((index, current_gcd))
28          
29            # Update `gcds` with the latest gcds discovered
30            gcds = temp_gcds
31            # Append the current number as a starting point for a new sequence
32            gcds.append((i, num))
33          
34            # Iterate over our list of gcds
35            for index, gcd_value in gcds:
36                # Check if we have at least `k` elements in our current sequence
37                if i - index + 1 >= k:
38                    # If the condition is satisfied, calculate the sum * gcd product
39                    current_sum = (prefix_sum[i + 1] - prefix_sum[index]) * gcd_value
40                    # Update the maximum sum if the current one is larger
41                    max_sum = max(max_sum, current_sum)
42      
43        # Return the maximum sum
44        return max_sum
45
1class Solution {
2  
3    // Function to calculate the maximum GCD sum in the array with subsequences of length at least 'k'
4    public long maxGcdSum(int[] nums, int k) {
5        int n = nums.length;
6        long[] prefixSum = new long[n + 1]; // Array to store prefix sums of 'nums'
7        // Calculate prefix sums
8        for (int i = 1; i <= n; ++i) {
9            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
10        }
11      
12        List<int[]> gcdSubsequences = new ArrayList<>(); // List to store [start index, gcd value] pairs
13        long maxResult = 0; // Initialize the max result to 0
14      
15        for (int i = 0; i < n; ++i) {
16            List<int[]> newGcdSubsequences = new ArrayList<>();
17          
18            // Update the existing gcd subsequences with the new element
19            for (int[] gcdPair : gcdSubsequences) {
20                int startIndex = gcdPair[0], currentGcd = gcdPair[1];
21                int newGcd = gcd(currentGcd, nums[i]);
22                // Add new gcd subsequence only if it is not the same as the last one in the list
23                if (newGcdSubsequences.isEmpty() || newGcdSubsequences.get(newGcdSubsequences.size() - 1)[1] != newGcd) {
24                    newGcdSubsequences.add(new int[] {startIndex, newGcd});
25                }
26            }
27          
28            // Replace the old list with the new list of gcd subsequences
29            gcdSubsequences = newGcdSubsequences;
30            // Add the current number as a new subsequence
31            gcdSubsequences.add(new int[] {i, nums[i]});
32            // Calculate the result for each subsequence and update the max result
33            for (int[] gcdPair : gcdSubsequences) {
34                int startIndex = gcdPair[0], sequenceGcd = gcdPair[1];
35                if (i - startIndex + 1 >= k) { // Check if the subsequence length is at least 'k'
36                    long sum = (prefixSum[i + 1] - prefixSum[startIndex]) * sequenceGcd;
37                    maxResult = Math.max(maxResult, sum); // Update max result
38                }
39            }
40        }
41        return maxResult; // Return the maximum result
42    }
43
44    // Helper function to calculate the greatest common divisor (GCD) of two numbers
45    private int gcd(int a, int b) {
46        return b == 0 ? a : gcd(b, a % b);
47    }
48}
49
1#include <vector>
2#include <algorithm>
3#include <utility> // For std::pair
4using namespace std;
5
6class Solution {
7public:
8    // Function to find the maximum GCD sum with subarrays of at least length k
9    long long maxGcdSum(vector<int>& nums, int k) {
10        int n = nums.size();
11        // Prefix sum array to hold the sums of elements up to each index
12        vector<long long> prefixSum(n + 1, 0);
13        for (int i = 1; i <= n; ++i) {
14            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
15        }
16        // Vector to store pairs of indices and their corresponding GCDs
17        vector<pair<int, int>> gcdPairs;
18        long long maxGcdSumResult = 0; // To store the result
19        // Iterate through the array to calculate the GCDs for all subarrays
20        for (int i = 0; i < n; ++i) {
21            vector<pair<int, int>> currentGcds;
22            // Update the gcdPairs list with current gcd values including nums[i]
23            for (auto [index, gcdValue] : gcdPairs) {
24                int newGcdValue = gcd(gcdValue, nums[i]);
25                // Only add a new gcd pair if it's not the same as the last one in the list
26                if (currentGcds.empty() || currentGcds.back().second != newGcdValue) {
27                    currentGcds.emplace_back(index, newGcdValue);
28                }
29            }
30            // Move the current GCD list to gcdPairs for next iteration
31            gcdPairs = move(currentGcds);
32            // Add the current element as a pair
33            gcdPairs.emplace_back(i, nums[i]);
34            // Calculate maximum gcd sum
35            for (auto [index, gcdValue] : gcdPairs) {
36                if (i - index + 1 >= k) {
37                    maxGcdSumResult = max(maxGcdSumResult, (prefixSum[i + 1] - prefixSum[index]) * gcdValue);
38                }
39            }
40        }
41        return maxGcdSumResult;
42    }
43  
44    // Helper function to calculate the gcd of two numbers
45    int gcd(int a, int b) {
46        while (b != 0) {
47            int temp = b;
48            b = a % b;
49            a = temp;
50        }
51        return a;
52    }
53};
54
1function maxGcdSum(numbers: number[], minimumSubsetSize: number): number {
2    const numbersCount: number = numbers.length;
3    // Initialize an array to store the prefix sums of the numbers array.
4    const prefixSums: number[] = Array(numbersCount + 1).fill(0);
5    for (let i = 1; i <= numbersCount; i++) {
6        prefixSums[i] = prefixSums[i - 1] + numbers[i - 1];
7    }
8
9    // Initialize an array to store tuples of (index, gcd value) from subsets
10    let gcdTuples: [number, number][] = [];
11    // Variable to keep track of the maximum sum times gcd found so far.
12    let maximumGcdSum: number = 0;
13
14    // Iterate over the numbers array.
15    for (let i = 0; i < numbersCount; ++i) {
16        // Initialize a temporary array for new gcd values found at the current step.
17        const newGcdTuples: [number, number][] = [];
18        // Find all possible gcds between the current element and elements of the existing gcd tuples.
19        for (const [index, gcdValue] of gcdTuples) {
20            const currentGcd: number = gcd(gcdValue, numbers[i]);
21            // Ensure the gcd value is updated only if it's different from the last one in new tuples.
22            if (newGcdTuples.length === 0 || newGcdTuples.at(-1)[1] !== currentGcd) {
23                newGcdTuples.push([index, currentGcd]);
24            }
25        }
26        // Replace old gcd tuples with the updated list.
27        gcdTuples = newGcdTuples;
28        // Add the current value as a new gcd tuple (initial set considered).
29        gcdTuples.push([i, numbers[i]]);
30        // Iterate over gcd tuples and check if they meet the minimum subset size requirement.
31        for (const [index, gcdValue] of gcdTuples) {
32            if (i - index + 1 >= minimumSubsetSize) {
33                // Calculate sum of the subset multiplied by the gcd and update the maximum if necessary.
34                maximumGcdSum = Math.max(maximumGcdSum, (prefixSums[i + 1] - prefixSums[index]) * gcdValue);
35            }
36        }
37    }
38
39    // Return the maximum of the product of sum of subset and its gcd among all subsets checked.
40    return maximumGcdSum;
41}
42
43function gcd(a: number, b: number): number {
44    // Recursive function to calculate the gcd (greatest common divisor) of two numbers.
45    return b === 0 ? a : gcd(b, a % b);
46}
47
Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The provided Python code defines a method maxGcdSum which takes an integer list nums and an integer k as its parameters. This method calculates the maximum possible sum of any subsequence of nums with length at least k where this sum is multiplied by the greatest common divisor (GCD) of the elements in this subsequence.

Time Complexity

The time complexity of the given code can be analyzed as follows:

  • Calculating the prefix sum s using accumulate takes O(n) time, where n is the length of the nums list.

  • The outer loop runs n times, once for each element in nums.

  • Inside the outer loop, there's an inner loop that iterates through f, a list of tuples containing index and GCD till that index. In the worst case, each element in nums could be appended to f, which, in the worst case, means we can have a nested loop situation. However, due to the property that the GCD of any new number with the previous GCDs will either stay the same or reduce (and we only maintain unique GCDs), the total number of unique GCDs we will have to maintain would be at most log(maxValue), where maxValue is the maximum value in nums. This is based on the number of times a number can be halved before reaching 1.

  • The inner loop also contains the computation of the GCD, an operation that in the worst case could be O(log(min(a, b))) where a and b are the two numbers. However, in practice, this is generally much faster and is considered effectively constant for small numbers.

  • There is also a maximum computation which is O(1) but nested within the loop.

Combining these considerations gives us a time complexity of O(n * log(maxValue) * log(min(a, b))) where a and b are the elements of nums.

Space Complexity

The space complexity is considered by analyzing the space or extra memory used by the algorithm outside of the input data.

  • We're maintaining the prefix sums with s, which takes O(n) extra space.

  • The list f will store at most log(maxValue) unique greatest common divisors paired with their respective index for each of the n elements, giving us an additional O(n * log(maxValue)) space.

So, the total space complexity can be approximated to O(n * log(maxValue)).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫