Given an array arr[] of N integers and a number K, the task is to find the sum of absolute difference of all pairs raised to the power K in a given array i.e., ![\sum_{i=1}^{N} \sum_{j=1}^{N} \ |arr[i]-arr[j]|^K](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-b8cc221f9a0cbe10ec84f2db349d6753_l3.png "Rendered by QuickLaTeX.com")
.
Examples:
Input: arr[] = {1, 2, 3}, K = 1
Output: 8
Explanation:
Sum of |1-1|+|1-2|+|1-3|+|2-1|+|2-2|+|2-3|+|3-1|+|3-2|+|3-3| = 8
Input: arr[] = {1, 2, 3}, K = 3
Output: 20
Explanation:
Sum of |1 – 1| 3 + |1 – 2| 3 + |1 – 3| 3 + |2 – 1| 3 + |2 – 2| 3 + |2 – 3| 3 + |3 – 1| 3 + |3 – 2| 3 + |3 – 3| 3 = 20
Naive Approach: The idea is to generate all the possible pairs and find the absolute difference of each pair raised to the power K and sum up them together.
Time Complexity: O((log K)*N2)
Auxiliary Space: O(1)
Efficient Approach: We can improve the time complexity of the naive approach with the below calculations:
For all possible pair, we have to find the value of
![Sum = \sum_{i=1}^{N} \sum_{j=1}^{N} |arr[i] - arr[j]|^{K}](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-d5ec86dd4817ca810b9b994485226773_l3.png "Rendered by QuickLaTeX.com")
Since for pairs (arr[i], arr[j]) the value of ![|arr[i]-arr[j]|^{K}](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_quicklatex.com-7a02fec4277b14b58ec98e1e028622c5_l3.png "Rendered by QuickLaTeX.com")
is being calculated twice. So the above equation can also be written as:
![Sum = 2 * \sum_{i=1}^{N} \sum_{j=1}^{i-1} |arr[i] - arr[j]|^{K}](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_quicklatex.com-ed6969a98d1cad2f7068792b5563f7d9_l3.png "Rendered by QuickLaTeX.com")
Writing in terms of Binomial Equation:
(Equation 1)
![Sum = 2 * \sum_{i=1}^{N} \sum_{j=1}^{i-1} \sum_{a=0}^{K} \binom{K}{a}arr[i]^{K}*(-arr[j])^{K - a}](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-673cbfbbecef41303bc9a770020a9a99_l3.png "Rendered by QuickLaTeX.com")
(Equation 1) Let Pre[i][a] = ![\sum_{j=1}^{i-1}(-arr[j])^{K - a}](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-3ca20caa5de09d82fc7bde50ab761074_l3.png "Rendered by QuickLaTeX.com")
(Equation 2)
From Equation 1 and Equation 2, we have
![Sum = 2 * \sum_{i=1}^{N} \sum_{a=0}^{K} \binom{K}{a}Pre[i][a]*arr[i]^{K}](https://geeksforgeeks.org/wp-content/uploads/2023/10/rubhabha_quicklatex.com-dca9403b2b7275677ba770995a2e010d_l3.png "Rendered by QuickLaTeX.com")
The value of Pre[i][a] can be calculated as:
Pre[i][a] = {(-arr[1])K – a + (-arr[2])K – a … . . +(-arr[i – 1])K – a}.
So, Pre[i+1][a] = Pre[i][a]+(-arr[i])K – a
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;class Solution {public: // Since K can be 100 max ll ncr[101][101]; int n, k; vector<ll> A; // Constructor Solution(int N, int K, vector<ll> B) { // Initializing with -1 memset(ncr, -1, sizeof(ncr)); n = N; k = K; A = B; // Making vector A as 1-Indexing A.insert(A.begin(), 0); } ll f(int N, int K); ll pairsPower();};// To Calculate the value nCkll Solution::f(int n, int k){ if (k == 0) return 1LL; if (n == k) return 1LL; if (n < k) return 0; if (ncr[n][k] != -1) return ncr[n][k]; // Since nCj = (n-1)Cj + (n-1)C(j-1); return ncr[n][k] = f(n - 1, k) + f(n - 1, k - 1);}// Function that summation of absolute// differences of all pairs raised// to the power kll Solution::pairsPower(){ ll pre[n + 1][k + 1]; ll ans = 0; // Sort the given array sort(A.begin() + 1, A.end()); // Precomputation part, O(n*k) for (int i = 1; i <= n; ++i) { pre[i][0] = 1LL; for (int j = 1; j <= k; j++) { pre[i][j] = A[i] * pre[i][j - 1]; } if (i != 1) { for (int j = 0; j <= k; ++j) pre[i][j] = pre[i][j] + pre[i - 1][j]; } } // Traverse the array arr[] for (int i = n; i >= 2; --i) { // For each K for (int j = 0; j <= k; j++) { ll val = f(k, j); ll val1 = pow(A[i], k - j) * pre[i - 1][j]; val = val * val1; if (j % 2 == 0) ans = (ans + val); else ans = (ans - val); } } ans = 2LL * ans; // Return the final answer return ans;}// Driver Codeint main(){ // Given N and K int N = 3; int K = 3; // Given array vector<ll> arr = { 1, 2, 3 }; // Creation of Object of class Solution obj(N, K, arr); // Function Call cout << obj.pairsPower() << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;public class GFG{ // Since K can be 100 max static long[][] ncr = new long[101][]; static int n, k; static long A[]; // To Calculate the value nCk static long f(int n, int k) { if (k == 0) return (long)1; if (n == k) return (long)1; if (n < k) return 0; if (ncr[n][k] != -1) return ncr[n][k]; ncr[n][k] = f(n - 1, k) + f(n - 1, k - 1); // Since nCj = (n-1)Cj + (n-1)C(j-1); return ncr[n][k]; } // Function that summation of absolute // differences of all pairs raised // to the power k static long pairsPower() { long[][] pre = new long[n + 1][]; long ans = 0; for(int i = 0 ; i <= n ; i++){ pre[i] = new long[k + 1]; } // Sort the given array Arrays.sort(A,1,A.length); // Precomputation part, O(n*k) for (int i = 1 ; i <= n ; ++i) { pre[i][0] = (long)1; for (int j = 1 ; j <= k ; j++) { pre[i][j] = A[i] * pre[i][j - 1]; } if (i != 1) { for (int j = 0 ; j <= k ; ++j){ pre[i][j] = pre[i][j] + pre[i - 1][j]; } } } // Traverse the array arr[] for (int i = n ; i >= 2 ; --i) { // For each K for (int j = 0 ; j <= k ; j++) { long val = f(k, j); long val1 = (long)(Math.pow(A[i], k - j)) * pre[i - 1][j]; val = val * val1; if (j % 2 == 0) ans = (ans + val); else ans = (ans - val); } } ans = (long)(2) * ans; // Return the final answer return ans; } // Driver code public static void main(String[] args){ // Given N and K n = 3; k = 3; // Initializing with -1 for(int i = 0 ; i <= 100 ; i++){ ncr[i] = new long[101]; for(int j = 0 ; j <= 100 ; j++){ ncr[i][j] = -1; } } // Given array // Making vector A as 1-Indexing // So adding 0 in the beginning A = new long[]{ 0, 1, 2, 3 }; // Function Call System.out.println(pairsPower()); }}// This code is contributed by aadityaburujwale. |
Python3
# Python3 program for the above approachclass Solution: def __init__(self, N, K, B): self.ncr = [] # Since K can be 100 max for i in range(101): temp = [] for j in range(101): # Initializing with -1 temp.append(-1) self.ncr.append(temp) self.n = N self.k = K # Making vector A as 1-Indexing self.A = [0] + B # To Calculate the value nCk def f(self, n, k): if k == 0: return 1 if n == k: return 1 if n < k: return 0 if self.ncr[n][k] != -1: return self.ncr[n][k] # Since nCj = (n-1)Cj + (n-1)C(j-1); self.ncr[n][k] = (self.f(n - 1, k) + self.f(n - 1, k - 1)) return self.ncr[n][k] # Function that summation of absolute # differences of all pairs raised # to the power k def pairsPower(self): pre = [] for i in range(self.n + 1): temp = [] for j in range(self.k + 1): temp.append(0) pre.append(temp) ans = 0 # Sort the given array self.A.sort() # Precomputation part, O(n*k) for i in range(1, self.n + 1): pre[i][0] = 1 for j in range(1, self.k + 1): pre[i][j] = (self.A[i] * pre[i][j - 1]) if i != 1: for j in range(self.k + 1): pre[i][j] = (pre[i][j] + pre[i - 1][j]) # Traverse the array arr[] for i in range(self.n, 1, -1): # For each K for j in range(self.k + 1): val = self.f(self.k, j) val1 = (pow(self.A[i], self.k - j) * pre[i - 1][j]) val = val * val1 if j % 2 == 0: ans = ans + val else: ans = ans - val ans = 2 * ans # Return the final answer return ans# Driver codeif __name__ == '__main__': # Given N and K N = 3 K = 3 # Given array arr = [ 1, 2, 3 ] # Creation of object of class obj = Solution(N, K, arr) # Function call print(obj.pairsPower())# This code is contributed by Shivam Singh |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Since K can be 100 max static long[][] ncr = new long[101][]; static int n, k; static List<long> A; // To Calculate the value nCk static long f(int n, int k) { if (k == 0) return (long)1; if (n == k) return (long)1; if (n < k) return 0; if (ncr[n][k] != -1) return ncr[n][k]; ncr[n][k] = f(n - 1, k) + f(n - 1, k - 1); // Since nCj = (n-1)Cj + (n-1)C(j-1); return ncr[n][k]; } // Function that summation of absolute // differences of all pairs raised // to the power k static long pairsPower() { long[][] pre = new long[n + 1][]; long ans = 0; for(int i = 0 ; i <= n ; i++){ pre[i] = new long[k + 1]; } // Sort the given array A.Sort(1, A.Count - 1, Comparer<long>.Default); // Precomputation part, O(n*k) for (int i = 1 ; i <= n ; ++i) { pre[i][0] = (long)1; for (int j = 1 ; j <= k ; j++) { pre[i][j] = A[i] * pre[i][j - 1]; } if (i != 1) { for (int j = 0 ; j <= k ; ++j){ pre[i][j] = pre[i][j] + pre[i - 1][j]; } } } // Traverse the array arr[] for (int i = n ; i >= 2 ; --i) { // For each K for (int j = 0 ; j <= k ; j++) { long val = f(k, j); long val1 = (long)(Math.Pow(A[i], k - j)) * pre[i - 1][j]; val = val * val1; if (j % 2 == 0) ans = (ans + val); else ans = (ans - val); } } ans = (long)(2) * ans; // Return the final answer return ans; } // Driver code public static void Main(string[] args){ // Given N and K n = 3; k = 3; // Initializing with -1 for(int i = 0 ; i <= 100 ; i++){ ncr[i] = new long[101]; for(int j = 0 ; j <= 100 ; j++){ ncr[i][j] = -1; } } // Given array // Making vector A as 1-Indexing // So adding 0 in the beginning A = new List<long>{ 0, 1, 2, 3 }; // Function Call Console.WriteLine(pairsPower()); }} |
Javascript
// Javascript program for the above approach// To Calculate the value nCkfunction f(n, k){ if (k == 0) return 1; if (n == k) return 1; if (n < k) return 0; if (ncr[n][k] != -1) return ncr[n][k]; ncr[n][k] = f(n - 1, k) + f(n - 1, k - 1); // Since nCj = (n-1)Cj + (n-1)C(j-1); return ncr[n][k];}// Function that summation of absolute// differences of all pairs raised// to the power kfunction pairsPower(){ let pre=[]; let ans=0; for(let i = 0 ; i <= n ; i++){ let temp=[]; for(let j = 0 ; j <= k; j++){ temp.push(0); } pre.push(temp); } // Sort the given array A.sort(); // Precomputation part, O(n*k) for (let i = 1 ; i <= n ; ++i) { pre[i][0] = 1; for (let j = 1 ; j <= k ; j++) { pre[i][j] = A[i] * pre[i][j - 1]; } if (i != 1) { for (let j = 0 ; j <= k ; ++j){ pre[i][j] = pre[i][j] + pre[i - 1][j]; } } } // Traverse the array arr[] for (let i = n ; i >= 2 ; --i) { // For each K for (let j = 0 ; j <= k ; j++) { let val = f(k, j); let val1 = (Math.pow(A[i], k - j)) * pre[i - 1][j]; val = val * val1; if (j % 2 == 0) ans = (ans + val); else ans = (ans - val); } } ans = (2) * ans; // Return the final answer return ans;}// Driver code // Given N and K let n = 3; let k = 3; let ncr = []; // Initializing with -1 for(let i = 0 ; i <= 100 ; i++){ let temp=[]; for(let j = 0 ; j <= 100 ; j++){ temp.push(-1); } ncr.push(temp); } // Given array // Making vector A as 1-Indexing // So adding 0 in the beginning A = [0, 1, 2, 3]; // Function Call console.log(pairsPower());// This code is contributed by Pushpesh Raj. |
Output:
20
Time Complexity: O(N*K)
Auxiliary Space: O(N*K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
