Missing Test Case - 3574. Maximize Subarray GCD Score #29716
Description
LeetCode Username
Nishan10
Problem Number, Title, and Link
- Maximize Subarray GCD Score. https://leetcode.com/problems/maximize-subarray-gcd-score/description/
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
The following test case:
nums=[1,5,8,5,8,5,8,5,8] and k=5
This test case should give the correct output as 18 as we can multiply the elements at index 0,1,3,5,7 by 2. This will result in the gcd of the entire array being 2 and therefore maximum score can be achieved by taking the entire array as 2*9=18. However my below code gives the answer as 16 which is incorrect. And this code gets accepted when submitted. Please consider and add this test case for this question.
Language Used for Code
C++
Code used for Submit/Run operation
class Solution {
public:
long long maxGCDScore(vector<int>& nums, int k) {
int n=nums.size();
long long maxi=0;
for(auto it: nums){
maxi=max(maxi,1ll*it);
}
maxi=2*maxi;
int i=0, j=0;
while(j<n){
int cnt=0;
while(j<n && nums[i]==nums[j]){
cnt++;
j++;
}
int len=j-i;
maxi=max(maxi,1ll*len*nums[i]);
maxi=max(maxi,1ll*min(len,k)*nums[i]*2);
i=j;
}
for(int i=0; i<n; i++){
int j=i+1, p=i-1, len=0, c=0, x=0;
for( ; j<n; j++){
if(nums[j]%nums[i]==0){
;
}
else if(nums[j]*2%nums[i]==0){
if(c<k){
c++;
}
else{
x++;
break;
}
}
else{
break;
}
}
len+=j-i;
for( ; p>=0; p--){
if(nums[p]%nums[i]==0){
;
}
else if(nums[p]*2%nums[i]==0){
if(c<k){
c++;
}
else{
x++;
break;
}
}
else{
break;
}
}
len+=i-p-1;
maxi=max(maxi,1ll*len*nums[i]);
}
int g=0;
for(auto it: nums){
g=__gcd(it,g);
}
maxi=max(maxi,1ll*g*n);
for(int i=0; i<n; i++){
if(k>0){
nums[i]=nums[i]*2;
k--;
}
else{
break;
}
}
g=0;
for(auto it: nums){
g=__gcd(it,g);
}
maxi=max(maxi,1ll*g*n);
return maxi;
}
};Expected behavior
The code gets accepted. However for the above testcase, the correct answer is 18 but the code gives the answer as 16 which is incorrect.
Screenshots
Additional context
No response