# Nested loops complexity reduction

My Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()

{

fast

int t;

cin>>t;

while(t--)

{

ll n;

cin>>n;

ll count=0;

ll arr[n];

for(ll i=0;i<n;i++){

cin>>arr[i];

}

for(ll i=0;i<n;i++){

for(ll j=i+1;j<n;j++){

if(arr[j]-arr[i]==j-i){

count++;

}

}

}

cout<<count<<endl;

}

return 0;

}


I was getting an TLE on test 4 /5.
As Time limit was 2 seconds ,my code was O(n^2) hence it must have passed all the test cases .
Kindly Help(Correct my code).

1 Like

Your approach is too naive to pass.

Observe that a_j - a_i = j - i implies a_j - j = a_i - i. Therefore you can store the values of a_j - j in a map. Now for same values of a_j - j, you need to add {cnt \choose 2} to answer where cnt is the count of values.
Do you want the code or you want to try it once more?

1 Like

Yeah senior, I agree. But Can’t this code can be easily passed in 2 secs?
The sum over all test cases were 2*10^5

I Will try, senior.

But there were 10^4 test cases , i.e. overall complexity is \mathcal{O}(TN^2) hence 10^4 \times 2 \times 10^5 =2 \times 10^9 which is more than 2\times 10^8. Your code’s estimated runtime would be 10 seconds.

Though, I think 10^8 iterations can be done in one second in CPP. Correct me if i am wrong.

Yes and so in 2 seconds 2\times 10^8 operations can be processed. But you are doing 2\times 10^9. In fact more than that as \displaystyle \sum N\le2\times10^5 so \displaystyle \sum N^2 would be of the order 10^{10} which is anyways more than 2\times 10^8

2 Likes

Got it.