Subtraction of sorted data

Question

I have a sorted array X[k]. Now I want to find

I have tried this

    int ans=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            ans+=abs(X[i]-X[j]);
        }
    }

I'm getting the correct answer by using the above solution, but it's not optimized, In some case Time limit exceeded. Is there any algorithm for implementing this in minimum complexity?

Answer 1

We need to calculate: Sigma[i] Sigma[j>i] abs(Xi-Xj). (Indices i,j are assumed to be between 1 and k everywhere).

Because the array is sorted, Xj>=Xi for j>i. This allows you to get rid of the abs, so that you have:

Sigma[i] Sigma[j>i] (Xj - Xi)

This can be separated to two sums:

Sigma[i] Sigma[j>i] Xj  -  Sigma[i] Sigma[j>i] Xi

For a specific j, how many times does Xj appear in the first sum? X2 appears once (only for i=1 and j=2), X3 appears twice (i=1,j=3 and i=2,j=3), etc. In general, Xj appears j-1 times, so it contributes (j-1)Xj to the sum (assuming 1-based indexing).

In the same manner, Xi appears (k-i) times in the second sum, so contributes (k-i)Xi to the total.

This gives the result: Sigma[j](j-1)Xj - Sigma[i](k-i)Xi. This can be simplified to:

Sigma[i]((2i-k-1)Xi)

This is calculated in O(n), instead of O(n^2) for the trivial algorithm.