Number of indices pair such that element pair sum from first Array is greater than second Array | Python 3 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
import bisect NEW_LINE def getPairs ( A , B , n ) : NEW_LINE INDENT D = [ 0 ] * ( n ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT D [ i ] = A [ i ] - B [ i ] NEW_LINE DEDENT D . sort ( ) NEW_LINE total = 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( D [ i ] > 0 ) : NEW_LINE INDENT total += n - i - 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = bisect . bisect_right ( D , - D [ i ] , 0 , len ( D ) ) NEW_LINE total += n - k NEW_LINE DEDENT DEDENT return total NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE A = [ ] NEW_LINE B = [ ] NEW_LINE A . append ( 4 ) ; NEW_LINE A . append ( 8 ) ; NEW_LINE A . append ( 2 ) ; NEW_LINE A . append ( 6 ) ; NEW_LINE A . append ( 2 ) ; NEW_LINE B . append ( 4 ) ; NEW_LINE B . append ( 5 ) ; NEW_LINE B . append ( 4 ) ; NEW_LINE B . append ( 1 ) ; NEW_LINE B . append ( 3 ) ; NEW_LINE print ( getPairs ( A , B , n ) ) NEW_LINE DEDENT