Optimizing number of pairs

general
,
1

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?

2

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

3

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
4

Can you share the code?

6 
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;
}