Sum of absolute difference of all pairs raised to power K

19 June 2025

0

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$ .
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| ³ + |1 – 2| ³ + |1 – 3| ³ + |2 – 1| ³ + |2 – 2|³ + |2 – 3|³ + |3 – 1|³ + |3 – 2|³ + |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)*N²)
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}$

Since for pairs (arr[i], arr[j]) the value of $|arr[i]-arr[j]|^{K}$ 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}$

Writing $|arr[i]-arr[j]|^{K}$ in terms of Binomial Equation:

$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}$ (Equation 1)

Let Pre[i][a] = $\sum_{j=1}^{i-1}(-arr[j])^{K - a}$ (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}$

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 long
using 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 nCk
ll 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 k
ll 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 Code
int 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 approach
class 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 code
if __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 approach
using 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 nCk
function 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 k
function 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:

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!

Sum of absolute difference of all pairs raised to power K

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US