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 a = new ArrayList(); //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.

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:

• add a1 zero times, a2 once,... ak k-1 times, and

• 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.

StackExchange Code Review Q#32937, answer score: 13