# Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array

Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements.

Given 4 elements (1, 2, 3 and 4):

|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10

Here is my code in Java:

List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers
public static int lsum(int N)
{
int sum =0;

for( int i=0;i<N;i++)
{
int w =a.get(i);
for(int j =i;j<N;j++)
{
int z = a.get(j);
sum =sum +(z-w);
}

}
return(sum);

}


I'm looking for an efficient algorithm rather than the trivial one I am using (O(n2) complexity). This is a requirement for a bigger program which requires this function. The input (number of elements) can be as big as 105.

• 1. What is min? 2. Don't you need abs somewhere? 3. Do we know anything about the numbers in the array (i.e., their span, distribution,...)? 4. Setting j=i+1 instead of j=i will save you N steps. – Vedran Šego Oct 19 '13 at 22:08
• @VedranŠego 1. corrected. 2. Consider the list to be sorted in ascending order. 3. k< 10^5 that is all that's given. 4. Thanks for the save, however when the input size is considered the (10^5) does not really help in reducing O(n^2) complexity – Sushim Mukul Dutta Oct 19 '13 at 22:48

Let's see this mathematically. I am assuming that a is an ascendingly sorted array. I start with indexes from 1, to get better readability (by avoiding n-1 as often as possible).

We want the following sum:

$$\begin{array}{l@{}l@{}l@{}l} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_j - a_i) = (a_2 - a_1) &+ (a_3 - a_1) &+ (a_4 - a_1) + & \dots + (a_n - a_1) +\\ &+ (a_3 - a_2) &+ (a_4 - a_2) + & \dots + (a_n - a_2) +\\ &&+ (a_4 - a_3) + & \dots + (a_n - a_3) +\\ &&& \dots \end{array}$$

So, we:

1. add a1 zero times, a2 once,... ak k-1 times, and
2. subtract a1 n-1 times, a2 n-2 times,... ak n-k times.

I'd say that your sum is

$$\sum_{k=1}^n (k-1)a_k - \sum_{k=1}^n (n-k)a_k = \sum_{k=1}^n (2k-n-1)a_k$$

Given your example (1,2,3,4), we get:

$$\sum_{k=1}^4 (2k-4-1)a_k = -3 \cdot 1 + (-1 \cdot 2) + 1 \cdot 3 + 3 \cdot 4 = -3 - 2 + 3 + 12 = 10.$$

This has a linear complexity, which is optimal, because you need to "visit" each member of the array at least once (which is linear).

I believe you can write your code by yourself. Just set indexes to go from zero, but be careful about the formula: 2k - n - 1 becomes 2k - n + 1 when k starts from zero.

• woah! Thanks a lot. The break up of the formula did the trick. – Sushim Mukul Dutta Oct 20 '13 at 18:48
• What should I say? excellent! – Thomas Junk Oct 20 '13 at 21:59