0

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 !

shubham goswami
  • 21
  • 8
  • 2
    An observation: once a subarray [i,j] is divisible by 4, any larger subarray that contains it is _also_ divisible by 4. – Botje Apr 10 '20 at 11:13
  • 2
    This reads like a typical puzzle from some online contest site. If your goal is to learn C++, you will not learn anything there. In nearly all cases, like this one, the correct solution requires knowing some kind of a mathematical or a programming trick. If you don't know what the trick is, and attempt to code a brute-force approach, your program runs forever, and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Apr 10 '20 at 11:14

2 Answers2

2

The question is asking for the number of subarrays whose product is odd (zero factors of two) or a multiple of four (at least two factors of two). We can also invert this: take the number of subarrays (2**N) and subtract the number of subarrays that have exactly one factor of two.

So, first preprocess the array and replace every number with its factors of two (ie 7 becomes 0, 8 becomes 3, etc). The question is then "how many subarrays sum to exactly one", which has a known solution.

Botje
  • 26,269
  • 3
  • 31
  • 41
  • ["two to the power N"](https://en.wikipedia.org/wiki/Power_set), or `pow(2,N)` if you prefer that notation. – Botje Apr 10 '20 at 11:49
  • `0 % 4 == 0`, but doesn't have 2 or more multiple of 2 ;) And 0 is also a special case to handle. – Jarod42 Apr 10 '20 at 18:21
  • @Botje Original array is 2 5 6 , if the array stands after processing the 2's factors will be: 1 0 0 , so what should be the answer ? – shubham goswami Apr 10 '20 at 21:07
  • 6 is also divisible by 2 ... So the preprocessed array would be [1, 0, 1] – Botje Apr 10 '20 at 22:22
  • @Botje sir can u please telll me in detail how the preprocessed array would be with some explainatory examples – shubham goswami Apr 10 '20 at 22:29
  • I did so in my answer. Simply count the number of times you can divide by 2 before you end up with an odd number. Please do try to solve this problem for yourself instead of begging for the solution, that is not what StackOverflow is about. – Botje Apr 10 '20 at 22:32
0

this question is directly linked to ( april long challenge) from codechef. i don't think its a good idea to ask directly here before the closing of contest (3:00 pm , 13/04/2020). please obey rules and regulations of codechef. you can check out at this link if you don't believe my words.
https://www.codechef.com/APRIL20B/problems/SQRDSUB or directly visit codechef april challenge (squared subsequence).

mr x
  • 21
  • 5