# Optimizing number of pairs

Given an integer X, find the number of pairs (i, j) such that A[i] + B[j] ≤ X

Note: It is given that the above question can be solved in O(n), also, we may assume that the array given are sorted. Here’s my approach:

``````int count_pairs(vector<ll> a, vector<ll> b, ll x)
{
int ap = 0,bp = 0;
int c = 0;
while(ap<a.size() && bp<b.size() && a[ap]+b[bp]<=x)
{
ap++;
bp++;
c=ap*ap;
}
while(ap<a.size() && a[ap]+b[0]<=x)
{
for(int i=0; i<bp; ++i)
{
if(a[ap]+b[i]>x)
break;
c++;
}
ap++;
}
return c;
}
``````

However, we can see that this is not an optimal solution. So what should be the approach?

For each A_i, binary search B for the largest value that satisfies the condition. Let’s say you find it at index j. Then, you can add j to final answer. (Here, i and j are 1-based indices.)
This should work in O(N*\log_2{N})
I am finding O(N).

Yeah I figured it using two pointers, one starting from end(j), the other one from beginning(i).
keep incrementing i till a[i]+b[j]<=x, and keep updating the counter simultaneously. Also decrement j when a[i]+b[j]>x. Make the loop run till i<a.size() && j>=0

1 Like

Can you share the code?

``````int getNumOfPairs(long long int n, vector<long long int> A, vector<long long int> B) {
int i = 0;
int j = B.size() - 1;
int result = 0;
while (i < A.size() && j >= 0) {
if (A[i] + B[j] <= n) {
result += (j+1);
i++;
} else {
j--;
}
}
return result;
}
``````