i tried to count the number of products which are odd or divisible by 4 , generated by all possible sub-arrays but my implementation get O(n^2)…. i need in O(n) time . I also tried to get some pattern but cant found it here is my code

```
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
int main()
{
lli testcases,x,M=1000000007;
cin>>testcases;
for(x=0;x<testcases;x++){
lli n,i,j,temp,count1=0;
cin>>n;
vector<lli>v;
for(i=0;i<n;i++){
cin>>temp;
v.push_back(temp);
}
for(i=0;i<n-1;i++){
if(v[i]%2!=0 || v[i]%4==0){
++count1;
}
temp=v[i];
for(j=i+1;j<v.size();j++){
temp*=v[j];
if(temp%2!=0 || temp%4==0){
++count1;
}
}
}
if(v[n-1]%2!=0 || v[n-1]%4==0){
++count1;
}
cout<<count1<<"\n";
count1=0;
}
return 0;
}
```

thanks in advance !

Please login or Register to submit your answer