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
function sum ( a , n ) { var cnt = new Map ( ) ; var ans = 0 , pre_sum = 0 ; for ( var i = 0 ; i < n ; i ++ ) { ans += ( i * a [ i ] ) - pre_sum ; pre_sum += a [ i ] ; if ( cnt . has ( a [ i ] - 1 ) ) ans -= cnt . get ( a [ i ] - 1 ) ; if ( cnt . has ( a [ i ] + 1 ) ) ans += cnt . get ( a [ i ] + 1 ) ; if ( cnt . has ( a [ i ] ) ) cnt . set ( a [ i ] , cnt . get ( a [ i ] ) + 1 ) else cnt . set ( a [ i ] , 1 ) } return ans ; } var a = [ 1 , 2 , 3 , 1 , 3 ] ; var n = a . length ; document . write ( sum ( a , n ) ) ;