In the image below, the sample test case 3 considers reduction in overall gcd to 1 as a valid change and counts the i’th element as a strong element.
However in the hints, it is clearly stated that change in few elements of this same case reduce the overall gcd to 1. But still these elements are not considered as strong elements.
Really confused with this clash! of sample case explanations
check the problem here: STRNG
@rawnit_kohli
heyy, plzz refer my c++ code for better understanding of the logic .
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--)
{
map<long long int,long long int> mp,mpr;
long long int n;
long long int ans=0;
cin>>n;
long long int a[n];
long long int g;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(i==0)
g=a[0];
g=__gcd(g,a[i]);
mp[i]=g;
}
g=a[n-1];
for(int i=n-1;i>=0;i--)
{
g=__gcd(g,a[i]);
mpr[i]=g;
}
if(g!=1)
cout<<n;
else
{
for(int i=0;i<n;i++)
{
if(i==0)
{
if(mpr[i+1]!=1)
ans++;
}
else if(i==n-1)
{
if(mp[i-1]!=1)
ans++;
}
else
{
int d=__gcd(mp[i-1],mpr[i+1]);
if(d!=1)
ans++;
}
}
cout<<ans;
}
cout<<endl;
}
}