Find no. of pairs in two arrays with a condition

help
,
1

Given two arrays A[ ] & B[ ] of size N and a number K, we have to find the no. of pairs ( A[i] , B[j] ) such that A[i] + B[j] <= K.

Please suggest a approach with minimum time complexity.

2

Sort both arrays. First check for first value of A[0] and find the max B[j] such that A[0] + B[j] <= K. Now add that j to result. Now for second value of A[] (A[1]) decrease that value of j till sum become less than k. Now add the value of j. Repeat this process for each A[i]. So, this will work in O(nlgn)

1 Like
3

Thanks…

4

Can you help me out in this question as well…It uses the same logic
https://www.codechef.com/viewsolution/33145523

This is the approach as mentioned in the second method in its editorial LOWSUM - Editorial

Why does this give TLE… and how could i get rid of it.
If I do this with a different approach using priority_queue…It works fine.