3574. Maximize Subarray GCD Score

Description

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 <= 1500
• 1 <= nums[i] <= 109
• 1 <= k <= n

Solutions

Solution 1: Enumeration + Mathematics

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 \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def maxGCDScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        cnt = [0] * n
        for i, x in enumerate(nums):
            while x % 2 == 0:
                cnt[i] += 1
                x //= 2
        ans = 0
        for l in range(n):
            g = 0
            mi = inf
            t = 0
            for r in range(l, n):
                g = gcd(g, nums[r])
                if cnt[r] < mi:
                    mi = cnt[r]
                    t = 1
                elif cnt[r] == mi:
                    t += 1
                ans = max(ans, (g if t > k else g * 2) * (r - l + 1))
        return ans

class Solution {
    public long maxGCDScore(int[] nums, int k) {
        int n = nums.length;
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            for (int x = nums[i]; x % 2 == 0; x /= 2) {
                ++cnt[i];
            }
        }
        long ans = 0;
        for (int l = 0; l < n; ++l) {
            int g = 0;
            int mi = 1 << 30;
            int t = 0;
            for (int r = l; r < n; ++r) {
                g = gcd(g, nums[r]);
                if (cnt[r] < mi) {
                    mi = cnt[r];
                    t = 1;
                } else if (cnt[r] == mi) {
                    ++t;
                }
                ans = Math.max(ans, (r - l + 1L) * (t > k ? g : g * 2));
            }
        }
        return ans;
    }

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

class Solution {
public:
    long long maxGCDScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> cnt(n);
        for (int i = 0; i < n; ++i) {
            for (int x = nums[i]; x % 2 == 0; x /= 2) {
                ++cnt[i];
            }
        }

        long long ans = 0;
        for (int l = 0; l < n; ++l) {
            int g = 0;
            int mi = INT32_MAX;
            int t = 0;
            for (int r = l; r < n; ++r) {
                g = gcd(g, nums[r]);
                if (cnt[r] < mi) {
                    mi = cnt[r];
                    t = 1;
                } else if (cnt[r] == mi) {
                    ++t;
                }
                long long score = static_cast<long long>(r - l + 1) * (t > k ? g : g * 2);
                ans = max(ans, score);
            }
        }

        return ans;
    }
};

func maxGCDScore(nums []int, k int) int64 {
    n := len(nums)
    cnt := make([]int, n)
    for i, x := range nums {
        for x%2 == 0 {
            cnt[i]++
            x /= 2
        }
    }

    ans := 0
    for l := 0; l < n; l++ {
        g := 0
        mi := math.MaxInt32
        t := 0
        for r := l; r < n; r++ {
            g = gcd(g, nums[r])
            if cnt[r] < mi {
                mi = cnt[r]
                t = 1
            } else if cnt[r] == mi {
                t++
            }
            length := r - l + 1
            score := g * length
            if t <= k {
                score *= 2
            }
            ans = max(ans, score)
        }
    }

    return int64(ans)
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

function maxGCDScore(nums: number[], k: number): number {
    const n = nums.length;
    const cnt: number[] = Array(n).fill(0);

    for (let i = 0; i < n; ++i) {
        let x = nums[i];
        while (x % 2 === 0) {
            cnt[i]++;
            x /= 2;
        }
    }

    let ans = 0;
    for (let l = 0; l < n; ++l) {
        let g = 0;
        let mi = Number.MAX_SAFE_INTEGER;
        let t = 0;
        for (let r = l; r < n; ++r) {
            g = gcd(g, nums[r]);
            if (cnt[r] < mi) {
                mi = cnt[r];
                t = 1;
            } else if (cnt[r] === mi) {
                t++;
            }
            const len = r - l + 1;
            const score = (t > k ? g : g * 2) * len;
            ans = Math.max(ans, score);
        }
    }

    return ans;
}

function gcd(a: number, b: number): number {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Comments