1class Solution {
2    public long maxGCDScore(int[] nums, int k) {
3        int n = nums.length;
4        int[] twosCount = new int[n];
5
6        // Count the number of factors of 2 for each number in nums
7        for (int i = 0; i < n; ++i) {
8            int value = nums[i];
9            while (value % 2 == 0) {
10                ++twosCount[i];
11                value /= 2;
12            }
13        }
14
15        long maxScore = 0;
16
17        // Consider all subarrays nums[l..r]
18        for (int left = 0; left < n; ++left) {
19            int currentGCD = 0;
20            int minTwosCount = Integer.MAX_VALUE;
21            int minTwosCountFrequency = 0;
22
23            for (int right = left; right < n; ++right) {
24                // Update the GCD for the current subarray
25                currentGCD = gcd(currentGCD, nums[right]);
26
27                // Track the minimum number of factors of 2 in the current window
28                if (twosCount[right] < minTwosCount) {
29                    minTwosCount = twosCount[right];
30                    minTwosCountFrequency = 1;
31                } else if (twosCount[right] == minTwosCount) {
32                    ++minTwosCountFrequency;
33                }
34
35                // Compute score according to the problem's rule
36                // If the minimum count frequency > k, use GCD as is, else multiply by 2
37                long windowLength = right - left + 1L;
38                long currentScore = windowLength * (minTwosCountFrequency > k ? currentGCD : currentGCD * 2L);
39
40                // Track the maximum score found
41                maxScore = Math.max(maxScore, currentScore);
42            }
43        }
44        return maxScore;
45    }
46
47    // Helper method to compute greatest common divisor (GCD) via Euclidean algorithm
48    private int gcd(int a, int b) {
49        return b == 0 ? a : gcd(b, a % b);
50    }
51}
52

1#include <vector>
2#include <algorithm>
3#include <numeric>
4#include <climits>
5using namespace std;
6
7class Solution {
8public:
9    long long maxGCDScore(vector<int>& nums, int k) {
10        int n = nums.size();
11        vector<int> twosCount(n);
12
13        // Count number of factors of 2 for each element in nums.
14        for (int i = 0; i < n; ++i) {
15            int x = nums[i];
16            while (x % 2 == 0) {
17                ++twosCount[i];
18                x /= 2;
19            }
20        }
21
22        long long result = 0; // Stores the maximum score found.
23
24        // Iterate through all subarrays.
25        for (int left = 0; left < n; ++left) {
26            int currentGCD = 0;           // GCD of current subarray.
27            int minTwos = INT_MAX;         // Minimal count of 2's in the subarray.
28            int minCount = 0;              // Frequency of the minimal count.
29
30            for (int right = left; right < n; ++right) {
31                // Update GCD of the current subarray.
32                currentGCD = gcd(currentGCD, nums[right]);
33
34                // Update minimum twos count and its frequency.
35                if (twosCount[right] < minTwos) {
36                    minTwos = twosCount[right];
37                    minCount = 1;
38                } else if (twosCount[right] == minTwos) {
39                    ++minCount;
40                }
41
42                // Calculate score for current subarray based on rules.
43                long long length = right - left + 1;
44                long long score = (minCount > k)
45                                ? length * currentGCD
46                                : length * currentGCD * 2;
47
48                result = max(result, score); // Update max score found
49            }
50        }
51
52        return result;
53    }
54};
55

1/**
2 * Calculates the greatest common divisor of two numbers.
3 * @param a First number
4 * @param b Second number
5 * @returns The greatest common divisor of a and b
6 */
7function gcd(a: number, b: number): number {
8    while (b !== 0) {
9        const temp = b;
10        b = a % b;
11        a = temp;
12    }
13    return a;
14}
15
16/**
17 * Finds the maximum score based on GCD and a constraint on the count of 2's in factorization.
18 * @param nums Array of numbers
19 * @param k Integer constraint
20 * @returns The maximum score satisfying the problem requirements
21 */
22function maxGCDScore(nums: number[], k: number): number {
23    const n: number = nums.length;
24    // cnt[i] holds the number of times 2 divides nums[i]
25    const cnt: number[] = Array(n).fill(0);
26
27    // Calculate the exponent of 2 in each number's factorization
28    for (let i = 0; i < n; ++i) {
29        let x: number = nums[i];
30        while (x % 2 === 0) {
31            cnt[i]++;
32            x /= 2;
33        }
34    }
35
36    let ans: number = 0;
37
38    // Try all subarrays [l, r] and keep track for each
39    for (let l = 0; l < n; ++l) {
40        let g: number = 0; // Current GCD of subarray [l, r]
41        let minExponent: number = Number.MAX_SAFE_INTEGER; // Minimum exponent of 2 in the current subarray
42        let minCount: number = 0; // Occurrence count of minExponent in [l, r]
43        for (let r = l; r < n; ++r) {
44            g = gcd(g, nums[r]);
45            // Update the minimum exponent and its occurrence count
46            if (cnt[r] < minExponent) {
47                minExponent = cnt[r];
48                minCount = 1;
49            } else if (cnt[r] === minExponent) {
50                minCount++;
51            }
52            const len: number = r - l + 1;
53            // If the number of elements with minExponent of 2 exceeds k, use g; otherwise, use g * 2
54            const score: number = (minCount > k ? g : g * 2) * len;
55            ans = Math.max(ans, score);
56        }
57    }
58
59    return ans;
60}
61