Garmaine Staff asked 2 years ago

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 !