Number of indices pair such that element pair sum from first Array is greater than second Array | C ++ program to find the number of indices pair such that pair sum from first Array is greater than second Array ; Function to get the number of pairs of indices { i , j } in the given two arrays A and B such that A [ i ] + A [ j ] > B [ i ] + B [ j ] ; Intitializing the difference array D ; Computing the difference between the elements at every index and storing it in the array D ; Sort the array D ; Variable to store the total number of pairs that satisfy the given condition ; Loop to iterate through the difference array D and find the total number of pairs of indices that follow the given condition ; If the value at the index i is positive , then it remains positive for any pairs with j such that j > i . ; If the value at that index is negative then we need to find the index of the value just greater than - D [ i ] ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getPairs ( vector < int > A , vector < int > B , int n ) { vector < int > D ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { D [ i ] = A [ i ] - B [ i ] ; } sort ( D . begin ( ) , D . end ( ) ) ; long long total = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( D [ i ] > 0 ) { total += n - i - 1 ; } else { int k = upper_bound ( D . begin ( ) , D . end ( ) , - D [ i ] ) - D . begin ( ) ; total += n - k ; } } return total ; } int main ( ) { int n = 5 ; vector < int > A ; vector < int > B ; A . push_back ( 4 ) ; A . push_back ( 8 ) ; A . push_back ( 2 ) ; A . push_back ( 6 ) ; A . push_back ( 2 ) ; B . push_back ( 4 ) ; B . push_back ( 5 ) ; B . push_back ( 4 ) ; B . push_back ( 1 ) ; B . push_back ( 3 ) ; cout << getPairs ( A , B , n ) ; }