I have read tutorial of SQRDSUB . And the time complexity mentioned isO( N) or O(N*logN)

But the constraints specify that

over all test cases N does not exceed 10^6

and there are 10^3 tests cases

then for O(N) there are 10^3 * 10^6 = 10^9 operations

how will O(N ) pass the test cases?

Yes, you are right. That approach would never be able to pass the test due to TLE.

So lets see to my code

Treat it as psudeocode please and btw this sol worked for me during the contest

```
#include<bits/stdc++.h>//author::@whohet-->Het Patel
#define int long long
using namespace std;
int sarrsum(int arr[], int n, int sum)
{
unordered_map<int, int> sum0;
int y = 0;
int sum1 = 0;
for (int i = 0; i < n; i++) {
sum1 += arr[i];
if (sum1 == sum)
y++;
if (sum0.find(sum1 - sum) !=
sum0.end())
y += (sum0[sum1 - sum]);
sum0[sum1]++;
}
return y;
}
signed main()
{
fasterthanlight;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n],a[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
if(arr[i]<0)
arr[i]=arr[i]*-1;
}
for(int i=0;i<n;i++)
{
int x=0;
while(arr[i]%2!=1 && arr[i]!=0)
{
arr[i]=arr[i]/2;
x++;
}
if(arr[i]==0)
x=2;
a[i]=x;
}
int sum=1;
int y=sarrsum(a,n,sum);
cout<<((n*(n+1))/2)-y<<endl;
}
}
```

+1

Your task is to find its time complexity

There are 10^3 test cases in one test file. The sum of N in each test file does not exceed 10^6.

I have a simple o(n) approach which worked during the contest…

#include <bits/stdc++.h>

using namespace std;

#include

#include <unordered_map>

#define ll long long int

#define pb push_back

#define po pop_back

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

int t;

cin>>t;

while(t–)

{

int n;

cin>>n;

int a[n+1];

for(int i=1;i<=n;i++)

cin>>a[i];

long long int count=0;

int flag1=0,flag2=0;

int key=0,key1=0;

for(int i=n;i>=1;i–)

{

if(a[i]%4==0)

{

flag1=0;

flag2=0;

key=n-i+1;

count+=key;

}

else if(a[i]%2==0)

{

if(flag2==1)

{

flag1=0;

key=key1;

key1=n-i+1;

count+=key;

}

else

{

flag1=0;

flag2=1;

key1=n-i+1;

count+=key;

}

}

else if(a[i]%2!=0)

{

flag1+=1;

count=count+key+flag1;

}

}

cout<<count<<endl;;

}

return 0;

}

I am a beginner and I am having difficulty understanding why O(n) would work in this case ?

What I am thinking is as there are 10^3 test cases and sum of N over all test cases is 10^6 it will take 10^9 operations

Please help me where I am going wrong

There are 10 or so test files. You can see your verdict in each test file when you submit. In each test file you are given T, the number of testcases in that test file. The sum of N over all test cases in a test file is less than 10^6

Sometimes 10^9 operations tends to pass in codechef if the operations u are doing are not very heavy and u are doing only basic math calculations it can pass time limit if you use fast in and fast out and \n instead of endl in my case

This solution passed the time limit with fastin and use of \n while otherwise it gave a tle

U can go through the code it’s well formatted and variables are named properly u can understand it easily.