Sum of absolute difference of all pairs raised to power K | Python3 program for the above approach ; Since K can be 100 max ; Initializing with - 1 ; Making vector A as 1 - Indexing ; To Calculate the value nCk ; Since nCj = ( n - 1 ) Cj + ( n - 1 ) C ( j - 1 ) ; ; Function that summation of absolute differences of all pairs raised to the power k ; Sort the given array ; Precomputation part , O ( n * k ) ; Traverse the array arr [ ] ; For each K ; Return the final answer ; Driver code ; Given N and K ; Given array ; Creation of object of class ; Function call
class Solution : NEW_LINE INDENT def __init__ ( self , N , K , B ) : NEW_LINE INDENT self . ncr = [ ] NEW_LINE for i in range ( 101 ) : NEW_LINE INDENT temp = [ ] NEW_LINE for j in range ( 101 ) : NEW_LINE INDENT temp . append ( - 1 ) NEW_LINE DEDENT self . ncr . append ( temp ) NEW_LINE DEDENT self . n = N NEW_LINE self . k = K NEW_LINE self . A = [ 0 ] + B NEW_LINE DEDENT def f ( self , n , k ) : NEW_LINE INDENT if k == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT if n == k : NEW_LINE INDENT return 1 NEW_LINE DEDENT if n < k : NEW_LINE INDENT return 0 NEW_LINE DEDENT if self . ncr [ n ] [ k ] != - 1 : NEW_LINE INDENT return self . ncr [ n ] [ k ] NEW_LINE DEDENT self . ncr [ n ] [ k ] = ( self . f ( n - 1 , k ) + self . f ( n - 1 , k - 1 ) ) NEW_LINE return self . ncr [ n ] [ k ] NEW_LINE DEDENT def pairsPower ( self ) : NEW_LINE INDENT pre = [ ] NEW_LINE for i in range ( self . n + 1 ) : NEW_LINE INDENT temp = [ ] NEW_LINE for j in range ( self . k + 1 ) : NEW_LINE INDENT temp . append ( 0 ) NEW_LINE DEDENT pre . append ( temp ) NEW_LINE DEDENT ans = 0 NEW_LINE self . A . sort ( ) NEW_LINE for i in range ( 1 , self . n + 1 ) : NEW_LINE INDENT pre [ i ] [ 0 ] = 1 NEW_LINE for j in range ( 1 , self . k + 1 ) : NEW_LINE INDENT pre [ i ] [ j ] = ( self . A [ i ] * pre [ i ] [ j - 1 ] ) NEW_LINE DEDENT if i != 1 : NEW_LINE INDENT for j in range ( self . k + 1 ) : NEW_LINE INDENT pre [ i ] [ j ] = ( pre [ i ] [ j ] + pre [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( self . n , 1 , - 1 ) : NEW_LINE INDENT for j in range ( self . k + 1 ) : NEW_LINE INDENT val = self . f ( self . k , j ) NEW_LINE val1 = ( pow ( self . A [ i ] , self . k - j ) * pre [ i - 1 ] [ j ] ) NEW_LINE val = val * val1 NEW_LINE if j % 2 == 0 : NEW_LINE INDENT ans = ans + val NEW_LINE DEDENT else : NEW_LINE INDENT ans = ans - val NEW_LINE DEDENT DEDENT DEDENT ans = 2 * ans NEW_LINE return ans NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE K = 3 NEW_LINE arr = [ 1 , 2 , 3 ] NEW_LINE obj = Solution ( N , K , arr ) NEW_LINE print ( obj . pairsPower ( ) ) NEW_LINE DEDENT