Count of Pairs in Arrays 'a' and 'b' with a Greater Sum in 'a'

Given two arrays a and b of the same size. Find the count of total pair in array a, such that the sum of elements of pair of array a is greater than the sum of elements of the corresponding pair of array b.

Example:

Input: a={5,7,4,8,11} b={3,6,1,9,13}
Output: 6
Explanation:
The pairs are (5,7)>(3,6), (5,7)>(3,6), (5,4)>(3,1), (5,8)>(3,9), (7,4)>(6,1), (4,8)>(1,9), (4,11)>(13,1)

Approach:
It is only possible when we count the total number of pairs of difference array( a_i– b_i), Whose sum is positive.

Generate a difference array diff_i=a_i-b_i.
Sort the difference array.
Take a variable ans=0 which stores required output.
Iterate over the positive integer of the difference array, such that for every ith iteration find an index j such that a[j]>-a[i] and increment ans with (i-j), since all the elements before j when paired with a[i] gives -ve sum.
print ans.

Implementation in C++:

#include<bits/stdc++.h>

using namespace std;
int positivepair(vector < int > & diff) {

  // Sorting the given array
  sort(diff.begin(), diff.end());

  // Variable to store the count of pairs
  int totalpair = 0;

  // Loop to iterate through the array
  for (int i = 0; i < diff.size(); i++) {

    // Since we have to consider only positive number 
    // We ignor negative number
    if (diff[i] <= 0)
      continue;

    // Finding the index j such that all numbers 
    // before index j give -ve sum when paired with diff[i]
    int j = lower_bound(diff.begin(), diff.end(), -diff[i] + 1) - diff.begin();

    totalpair += i - j;
  }
  return totalpair;

}
// Array to find the count of pair of 
// whose sum is greater than sum of crrosponding pair of b
int cplusplus(vector < int > & a, vector < int > & b) {
  // Array to take diffrence of every element 
  // of a and b respectively.
  vector < int > diff;
  // Loop to iterate through elements of both array 
  // and take the diffrence
  for (int i = 0; i < a.size(); i++) {
    diff.push_back(a[i] - b[i]);
  }
  return positivepair(diff);
}
//driver code
int main() {
  vector<int> a={5,7,4,8,11};
  vector<int> b={3,6,1,9,13};
  cout << cplusplus(a, b);
}

Output:

Time complexity: O(nlogn)
Space complexity: O(n)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.