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

Question

Given an array, find the sum of the absolute difference of every pair of integers.

For example: Given a[]= {2,3, 5, 7 };

output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.

It must be done better than O(n^2).

The original array isn't necessarily sorted.

Answer 1

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.

Answer 2

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;
    }