Storing frequency of each element and calculating sum simultaneously
for ( int i = 0 ; i < n ; i ++ ) { if ( mp . ContainsKey ( A [ i ] ) ) { var val = mp [ A [ i ] ] ; mp . Remove ( A [ i ] ) ; mp . Add ( A [ i ] , val + 1 ) ; sum += A [ i ] ; } else { mp . Add ( A [ i ] , 0 ) ; sum += A [ i ] ; } } for ( int i = 0 ; i < n ; ++ i ) { int k = sum - A [ i ] ; if ( k % 2 == 0 ) { k = k >> 1 ;