# Help in time complexity of SQRDSUB

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

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