Wrong answer in "CLPNT" please help!

help
,
1 
#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;
	        }
	    }```
Please Help!
2

use bianry search and lower bound else you will get TLE

1 Like
3

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

1 Like
4

for which test my code fails

5

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

6

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

Your Output:
0
0
0
-1

1 Like
7

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).

You Can Look at this Solution using Lower Bound:Click Here

1 Like
8

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

1 Like
9

Thanks a lot!
Your answer was very helpful!

1 Like
10

I am glad it was Helpful !