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)
Recommended: What is conio.h and why do we use?
Approach:
It is only possible when we count the total number of pairs of difference array( ai – bi ), Whose sum is positive.
- Generate a difference array diffi=ai-bi.
- 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:
6
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.