 ``````#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
long long  int n,i;
cin>>n;
long long int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
long long int q,a,b,sum,j,flag=0;
cin>>q;
for(i=0;i<q;i++)
{
sum=0;
cin>>a;
cin>>b;
sum=a+b;
for(j=0;j<n;j++)
{
if(sum==arr[j])
{
flag=1;
break;
}
else if(sum<arr[j])
{
flag=2;
break;
}

}
if(flag==0)
{
cout<<n<<endl;
}
else if(flag==1)
{
cout<<"-1"<<endl;
}
else
{
cout<<j<<endl;
}
}```

use bianry search and lower bound else you will get TLE

1 Like

Also you’ve written the code test case specific. You’ll need to generalise it.

1 Like

for which test my code fails

No, got wrong answer answer and i guess O(n) can work here as time limit is 1 second

Your Code Fails on Following Input:

``````1
2
3 2
4
1 0
0 1
2 0
1 2

Expected Output:
0
0
-1
-1
``````

0
0
0
-1

1 Like

Your Code is incorrect at this stage:

``````else if(sum<arr[j])
{
flag=2;
break;
}
``````

How come You know that How many lines are there before arr[j] as your array is not sorted.

2.You are not Updating flag=0 for every query.

If You Correct these two points Then You will get TLE

Your Code’s Complexity is O(Q * N) But Expected Complexity should be O(Q*(Log n))
So You should use Lower bound instead of following part in your code:

`````` for(j=0;j<n;j++)
{
if(sum==arr[j])
{
flag=1;
break;
}
else if(sum<arr[j])
{
flag=2;
break;
}

}
``````

Lower Bound will do this operation in O(Log n) [Array Should be Sorted] While you are doing it in O(n).

1 Like

Bro Your Code’s Complexity is NOT O(n) , it is O(Q * N),
Q- Number of Queries(Input Of Coordinates)

1 Like

Thanks a lot!