Difference of all possible pairs of numbers in an array

Suppose I have a reverse-sorted list of doubles: {3, 2, 1}

I want to find the sum of all the positive differences between possible pairs of numbers.
In this case, that would be (3-2)+(3-1)+(2-1) = 4.

I know that going through all the pairs is an option, but this takes O(n^2) time. Any idea on a better algorithm?

This is a very similar question that’s been answered, but I can’t quite find how to apply this to differences instead of sums.

>Solution :

The i-th element (with i = 0 .. n-1) in your sorted list will be

• added to the sum n-i-1 times
• substracted from the sum i times

So you can simply do

let sum = 0;
for (let i = 0; i < n; i++)
  sum = sum + (n-i-1) * list[i] - i * list[i]