Approach :
The main problem is reduced to this :
Count all subarrays in which the product modulo 4 is neither 2 nor -2, bcz only a no. which can’t be represented as a difference of two squares are only whose product modulo 4 ie., pro%4 ==2 or -2
From here : What's Possible?
More Specifically we can write this too… Count all subarrays in which there is only one value whose modulo 4 is 2 or -2 , no any other even value come in that subarray.
Count all invalid and subtract it from total subarrays possible.
1 For 20 marks just count all subarrays whose product modulo 4 is neither 2 nor -2
2 For 100 marks
A). Convert array into mod 4 array and count for each postion of ‘2’ or ‘-2’ how many continous odd values are there in left hand side(let it be x ) and how many continous odd values are there in right hand side (let it be y)
B). Let we called these subarrays be invalid , so for each 2 or -2 invalid subarray is
(x+1) * (y+1)
C.) Sum all these.
D). Total subarrays of array of length n is : (n*(n+1)/2)
E). Good subarrays = Total subarrays - (sum of all invalid subarrays )
I have applied the same logic but got WA, don’t know why can you find what is wrong in it? I was getting WA for both logics commented and uncommented one
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int t;
cin>>t;
while(t--)
{
long long int num;
cin>>num;
long long a[num],i,j,b[num];
for(i=0;i<num;i++)
{
cin>>b[i];
if(b[i]%2==1)
{
a[i]=0;
}
else if(b[i]%4==0)
{
a[i]=2;
}
else
{
a[i]=1;
}
}
long long int m=0;
vector<long long int> v;
for(i=0;i<num;i++)
{
if(a[i]==0)
{
m++;
}
if(a[i]==1)
{
v.push_back(m);
m=0;
}
if(a[i]==2)
{
v.push_back(m);
v.push_back(-1);
m=0;
}
}
if(a[num-1]!=2)
{
v.push_back(m);
}
long long ans=0;
for(i=1;i<v.size();i++)
{
if(v[i]==-1)
{
i++;
}
else
{
ans=ans+v[i]+v[i-1]+1+v[i]*v[i-1];
}
}
/* long long ans=0;
long long int m=0,n=0;
for(i=0;i<num;i++)
{
if(a[i]==1)
{
m=0;
n=0;
if(i==0)
{
m=0;
}
else
{
j=i-1;
while(j>=0)
{
if(a[j]>0)
break;
else
{
m++;
j--;
}
}
}
if(i==(num-1))
{
n=0;
}
else
{
j=i+1;
while(j<num)
{
if(a[j]>0)
break;
else
{
n++;
j++;
}
}
}
ans=ans+m+n+m*n+1;
}
}*/
long long an=num*(num+1)/2;
an=an-ans;
cout<<an<<endl;
}
}
An easier approach would be to keep a count of last two digits of products of all subarrays. Then check whether product%4==0 || product%2==1 is true and increment the result.
store all array by doing modulo 4 and then one simple approach is to find a sub-array which have single 2 and 0 count of zeros
,and this will not be counted as good sub-array,else all will be counted…