Maximize Subarray GCD Score - Practice Coding Problems

Maximize Subarray GCD Score - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,6,8], k = 1

› Output: 8

💡 Note: Double the element 8 to get [4,6,16]. The subarray [16] has GCD=16 and length=1, giving score 1×16=16. However, the subarray [4,6,8] originally has GCD=2 and length=3, score=6. After doubling 8: [4,6,16] has GCD=2, score=6. Best is subarray [8] doubled to [16] with score=16. Wait, let me recalculate: if we double 4→8, subarray [8,6,8] has GCD=2, score=6. Actually the subarray [8] alone (after doubling 8→16) gives score=16, which is maximum.

Example 2 — Multiple Operations

$ Input: nums = [2,4,6], k = 2

› Output: 12

💡 Note: Double elements at indices 0 and 1: [2,4,6] → [4,8,6]. The subarray [4,8] has GCD=4 and length=2, giving score 2×4=8. The subarray [4,8,6] has GCD=2 and length=3, giving score 3×2=6. Better: double 2→4 and 6→12: [4,4,12] subarray [4,4] has GCD=4, score=8. Actually [4] alone has score=4. Check [4,4,12]: GCD=4, but wait GCD([4,4,12])=4, score=12.

Example 3 — No Operations Needed

$ Input: nums = [12,12,12], k = 0

› Output: 36

💡 Note: No doubling allowed. The entire array [12,12,12] has GCD=12 and length=3, giving score 3×12=36.

Constraints

1 ≤ nums.length ≤ 10
1 ≤ nums[i] ≤ 100
0 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,6,8] with k=1 doubling operation

Process

Try doubling each element and find best subarray

Output

Maximum score = 16 from subarray [16]

Key Takeaway

🎯 Key Insight: Focus on individual subarrays and greedily optimize their GCD through strategic doubling

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to enumerate all subarrays and find optimal doubling strategy for each. For small arrays, we can afford to check all 2^n doubling combinations per subarray. Best approach is subarray enumeration with greedy optimization. Time: O(n⁴), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Enumerate Subarrays with Greedy Doubling	O(n⁴)	O(n)	For each subarray, greedily choose which elements to double to maximize GCD
Try All Combinations	O(2^n × n³)	O(n)	Try all possible ways to use k operations, then check all subarrays

Enumerate Subarrays with Greedy Doubling — Algorithm Steps

Enumerate all O(n²) subarrays
For each subarray, find optimal doubling strategy
Greedily double elements that maximize resulting GCD

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Subarray

Consider each possible contiguous subarray

Optimize GCD

Find best doubling strategy for this subarray

Calculate Score

Compute length × optimized GCD

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int popcount(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int findOptimalGCD(int* arr, int n, int operations) {
    if (n == 0) return 0;
    
    int maxGcd = 0;
    // Try all combinations of doubling up to 'operations' elements
    for (int mask = 0; mask < (1 << n); mask++) {
        if (popcount(mask) > operations) continue;
        
        // Create modified array
        int modified[n];
        for (int i = 0; i < n; i++) {
            modified[i] = arr[i];
            if (mask & (1 << i)) {
                modified[i] *= 2;
            }
        }
        
        // Calculate GCD
        int currentGcd = modified[0];
        for (int i = 1; i < n; i++) {
            currentGcd = gcd(currentGcd, modified[i]);
        }
        
        if (currentGcd > maxGcd) {
            maxGcd = currentGcd;
        }
    }
    
    return maxGcd;
}

int solution(int* nums, int n, int k) {
    int maxScore = 0;
    
    // Try all subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int length = j - i + 1;
            
            // Find best way to use up to k operations on this subarray
            int bestGcd = findOptimalGCD(&nums[i], length, min(k, length));
            int score = length * bestGcd;
            if (score > maxScore) {
                maxScore = score;
            }
        }
    }
    
    return maxScore;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

n² subarrays × n elements × n GCD calculations per optimization

✓ Linear Growth

Space Complexity

O(n)

Space for subarray and tracking doubled elements

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Enumerate Subarrays with Greedy Doubling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler