Sum of ( maximum element | PHP implementation of the above approach ; Function to return a ^ n % mod ; Compute sum of max ( A ) - min ( A ) for all subsets ; Sort the array . ; Maxs = 2 ^ i - 1 ; Mins = 2 ^ ( n - 1 - i ) - 1 ; Driver code
< ? php $ mod = 1000000007 ; function power ( $ a , $ n ) { global $ mod ; if ( $ n == 0 ) return 1 ; $ p = power ( $ a , $ n / 2 ) % $ mod ; $ p = ( $ p * $ p ) % $ mod ; if ( $ n & 1 ) { $ p = ( $ p * $ a ) % $ mod ; } return $ p ; } function computeSum ( & $ arr , $ n ) { global $ mod ; sort ( $ arr ) ; $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ maxs = ( power ( 2 , $ i ) - 1 + $ mod ) % $ mod ; $ maxs = ( $ maxs * $ arr [ $ i ] ) % $ mod ; $ mins = ( power ( 2 , $ n - 1 - $ i ) - 1 + $ mod ) % $ mod ; $ mins = ( $ mins * $ arr [ $ i ] ) % $ mod ; $ V = ( $ maxs - $ mins + $ mod ) % $ mod ; $ sum = ( $ sum + $ V ) % $ mod ; } return $ sum ; } $ arr = array ( 4 , 3 , 1 ) ; $ n = sizeof ( $ arr ) ; echo computeSum ( $ arr , $ n ) ; ? >