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.

CodePudding user response：

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]