1
$\begingroup$

Given a list of integers, how to find the sum of the differences of all possible pairs of numbers ?

For example if the number are $3,1,2$ then, answer should be $\lvert 3-1 \rvert + \lvert 3 -2 \rvert + \lvert 1-2 \rvert = 2 + 1 + 1 = 4 $

Suggest a suitable algorithm for this.

  • 0
    This is $\frac{n(n-1)}{2}$ times [Gini's mean difference](http://en.wikipedia.org/wiki/Mean_difference)2011-03-20

2 Answers 2

2

Try sorting the numbers and see if it helps.

  • 1
    Hint: if a > b then $|a-b| = a-b$; if a < b then $|a-b| = b-a$.2011-03-20
0

How do you define "suitable"? There is the simple approach of looping over all pairs, taking the absolute value of the difference, and accumulating. This is O(n^2). Do you think there is something better? As Yuval suggests, you can sort to avoid the absolute value.

  • 0
    @Henry: thanks. got it2011-03-20