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.

  • 0
    I did tried that but not getting any ideas for the next :(2011-03-20
  • 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
    Yes, there is something better. Yuval's suggestion wasn't just about avoiding the absolute value.2011-03-20
  • 1
    Indeed - you can take a weighted sum of the sorted values, where the weight is a simple function of the ranks and the number of values: for example $4 = 3 + 3 - 1 - 1$.2011-03-20
  • 0
    @Henry: thanks. got it2011-03-20