Finding sum of Absolute Difference of Every pair of integer from an array

note you add each number exactly k times (where k is its place if you sort the list)
also, you subtract each number exactly n-1-k times
you can sort the list (O(nlogn)) and then iterate over the sorted array, multiplying each element as mentioned above.

For example: Given a[]= {2,3, 5, 7 };
output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.

I suppose you could

• Sum the multiplication of each number starting backwards with #count - 1 to get the total
• Sum the multiplication of each number starting up front with #count - 1 to get the total to subtract

This would then become (7*3 + 5*2 +3*1) - (2*3 + 3*2 + 5*1) = 17

First of all array needs to be sorted in O(nlogn) time.

Now I would not give you the exact solution to this problem rather I would give you an intuition to solve this problem. If we try to generalize count of the number of times a particular number at index i is getting added and number of times it is being subtracted then for every index i we can use that mathematically derived formula to compute the sum of contributions of every number in the absolute difference in O(N) time and O(1) extra space.

You can refer to this video if you find difficulties in understanding this concept.

Video Link:- https://youtu.be/A4sz4kNDa-8

I think I have found the answer. I got it by looking into the result expression in my post.

Here is the code in C++.

    int AbsDiff(int a[], int n)
    {
      if ( n < 2 ) return 0;
      sort(a,a+n);     
      int sum = 0;
      int i;
      for(i=n-1;i>=0;i--)
      {
        sum += (a[i]*(i) - a[i]*(n-i-1));
      }
      return sum;
    }