Sum of f ( a [ i ] , a [ j ] ) over all pairs in an array of n integers | CPP program to calculate the sum of f ( a [ i ] , aj ] ) ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sum ( int a [ ] , int n ) { unordered_map < int , int > cnt ; int ans = 0 , pre_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans += ( i * a [ i ] ) - pre_sum ; pre_sum += a [ i ] ; if ( cnt [ a [ i ] - 1 ] ) ans -= cnt [ a [ i ] - 1 ] ; if ( cnt [ a [ i ] + 1 ] ) ans += cnt [ a [ i ] + 1 ] ; cnt [ a [ i ] ] ++ ; } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 1 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << sum ( a , n ) ; return 0 ; }