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.