Maximize Subarray GCD Score - Solution & Explanation
Problem Statement
You are given an array of positive integers nums and an integer k.
You may perform at most k operations. In each operation, you can choose one element in the array and double its value. Each element can be doubled at most once.
The score of a contiguous subarray is defined as the product of its length and the greatest common divisor (GCD) of all its elements.
Your task is to return the maximum score that can be achieved by selecting a contiguous subarray from the modified array.
Note:
- The greatest common divisor (GCD) of an array is the largest integer that evenly divides all the array elements.
Example 1:
Input: nums = [2,4], k = 1
Output: 8
Explanation:
- Double
nums[0]to 4 using one operation. The modified array becomes[4, 4]. - The GCD of the subarray
[4, 4]is 4, and the length is 2. - Thus, the maximum possible score is
2 × 4 = 8.
Example 2:
Input: nums = [3,5,7], k = 2
Output: 14
Explanation:
- Double
nums[2]to 14 using one operation. The modified array becomes[3, 5, 14]. - The GCD of the subarray
[14]is 14, and the length is 1. - Thus, the maximum possible score is
1 × 14 = 14.
Example 3:
Input: nums = [5,5,5], k = 1
Output: 15
Explanation:
- The subarray
[5, 5, 5]has a GCD of 5, and its length is 3. - Since doubling any element doesn't improve the score, the maximum score is
3 × 5 = 15.
Constraints:
1 <= n == nums.length <= 15001 <= nums[i] <= 1091 <= k <= n
Approach Overview
Problem Overview: You are given an integer array and must find the subarray that produces the maximum GCD-based score. The score depends on the greatest common divisor of the subarray combined with its length, so the goal is to evaluate subarrays efficiently without recomputing GCD values from scratch.
Approach 1: Brute Force Enumeration (O(n^3 log V) time, O(1) space)
The most direct approach enumerates every possible subarray and computes its GCD independently. For each pair of indices (i, j), iterate through the elements inside the range and compute the GCD from scratch using the Euclidean algorithm. After calculating the GCD, compute the score and track the maximum. This approach demonstrates the mathematical definition of GCD but performs repeated work because the same prefixes are recomputed many times. It quickly becomes impractical for large arrays.
Approach 2: Enumeration with Rolling GCD (O(n^2 log V) time, O(1) space)
A better strategy keeps the GCD while expanding the subarray. Fix a starting index i, then extend the subarray one element at a time. Update the running GCD using g = gcd(g, nums[j]) instead of recomputing the entire segment. Each extension requires only one GCD operation, which costs O(log V). This removes the inner recomputation loop and reduces the complexity to quadratic. This technique relies heavily on properties from number theory and works well when constraints allow O(nĀ²) enumeration.
Approach 3: Distinct GCD Compression (O(n log V) time, O(log V) space)
The optimal method uses the observation that the number of distinct GCD values for subarrays ending at a given index is small. Maintain a map or list of pairs representing (gcd_value, earliest_length) for all subarrays ending at the current index. When a new element arrives, compute new GCD values by combining it with previous ones and merge identical results. Each step only keeps distinct GCD states, which limits the count to roughly O(log V). This technique transforms the brute-force enumeration into a compressed dynamic process and is common in advanced array and math problems involving GCD propagation.
Recommended for interviews: Start with the rolling GCD enumeration to show understanding of how GCD behaves when extending a subarray. Then explain the distinct-GCD optimization that reduces the state space. Interviewers typically expect the compressed GCD approach because it demonstrates knowledge of number theory properties and efficient subarray enumeration.
Solution
We notice that the length of the array in this problem is n leq 1500, so we can enumerate all subarrays. For each subarray, calculate its GCD score and find the maximum value as the answer.
Since each number can be doubled at most once, the GCD of a subarray can be multiplied by at most 2. Therefore, we need to count the minimum number of factors of 2 among all numbers in the subarray, as well as the number of times this minimum occurs. If the count is greater than k, the GCD score is the GCD itself; otherwise, the GCD score is the GCD multiplied by 2.
Thus, we can preprocess the number of factors of 2 for each number, and when enumerating subarrays, maintain the current subarray's GCD, the minimum number of factors of 2, and the number of times this minimum occurs.
The time complexity is O(n^2 times log n) and the space complexity is O(n), where n is the length of the array nums.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3 log V) | O(1) | Useful only for understanding the definition of subarray GCD and verifying small inputs |
| Enumeration with Rolling GCD | O(n^2 log V) | O(1) | Practical when constraints allow quadratic enumeration |
| Distinct GCD Compression | O(n log V) | O(log V) | Best general solution for large arrays using number theory properties |
Video Solution
Leetcode | Biweekly Contest 158 | C | 3574. Maximize Subarray GCD Score | Easy Solution | Editorials ā¢ Pretest Passed ā¢ 898 views views
Watch 1 more video solutions āFrequently Asked Questions
Is Maximize Subarray GCD Score easy or hard?
Maximize Subarray GCD Score Python/Java solution
How to solve Maximize Subarray GCD Score in O(n)?
What is the best approach for Maximize Subarray GCD Score?
Is Maximize Subarray GCD Score asked at Google/Amazon/Meta?
What data structure is used in Maximize Subarray GCD Score?
What is the time complexity of Maximize Subarray GCD Score?
Ready to solve this problem?
Practice Maximize Subarray GCD Score with our built-in code editor and test cases.
Practice on FleetCode