Sum of f ( a [ i ] , a [ j ] ) over all pairs in an array of n integers | Function to calculate the sum ; map to keep a count of occurrences ; Traverse in the list from start to end number of times a [ i ] can be in a pair and to get the difference we subtract pre_sum . ; if the ( a [ i ] - 1 ) is present then subtract that value as f ( a [ i ] , a [ i ] - 1 ) = 0 ; if the ( a [ i ] + 1 ) is present then add that value as f ( a [ i ] , a [ i ] - 1 ) = 0 here we add as a [ i ] - ( a [ i ] - 1 ) < 0 which would have been added as negative sum , so we add to remove this pair from the sum value ; keeping a counter for every element ; Driver Code
def sum ( a , n ) : NEW_LINE INDENT cnt = dict ( ) NEW_LINE ans = 0 NEW_LINE pre_sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans += ( i * a [ i ] ) - pre_sum NEW_LINE pre_sum += a [ i ] NEW_LINE if ( a [ i ] - 1 ) in cnt : NEW_LINE INDENT ans -= cnt [ a [ i ] - 1 ] NEW_LINE DEDENT if ( a [ i ] + 1 ) in cnt : NEW_LINE INDENT ans += cnt [ a [ i ] + 1 ] NEW_LINE DEDENT if a [ i ] not in cnt : NEW_LINE INDENT cnt [ a [ i ] ] = 0 NEW_LINE DEDENT cnt [ a [ i ] ] += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 1 , 2 , 3 , 1 , 3 ] NEW_LINE n = len ( a ) NEW_LINE print ( sum ( a , n ) ) NEW_LINE DEDENT