CODEWITHSUNDEEP
arraysalgorithmdifference
LogicalX
LogicalX

Reputation: 95

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.

Upvotes: 1

Views: 687

Answers (1)

derpirscher
derpirscher

Reputation: 17382

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]

Upvotes: 2

Related Questions