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.

Answer 2

Assuming here sorted means

For any 1 ≤ i ≤ j ≤ N there is X _i ≤ X _j.

And denote the goal of your calculation as F

let F(X _1..N) = Σ _{1 ≤ i < j ≤ N} |X _i - X _j|

Then we have

F(X _1..N)
= F(X _2..N) + Σ _{1 ≤ i ≤ N}|X _i - X ₁|
= F(X _3..N) + Σ _{2 ≤ i ≤ N}|X _i - X ₂| + Σ _{1 ≤ i ≤ N}|X _i - X ₁|
= F(X _4..N) + ...

Notice

Σ _{k ≤ i ≤ N}|X _i - X _k|
= (N - k) × (X _{k + 1} - X _k) + Σ _{k + 1 ≤ i ≤ N}|X _i - X _{k + 1}|

So we have the following iteration to calculate the sum:

/* 
 * assuming here the data type int is suitable for holding the result
 * N is the array length, X is the sorted array
 */
int sorted_sub_sum(int N, const int *X)
{
    int ret = 0;
    int tmp_sum = 0;
    int i;
    for (i = 0; i < N; i++)
        tmp_sum += X[i] - X[0];
    for (i = 0; i < N - 1; i++)
    {
        ret += tmp_sum;
        tmp_sum -= (N - i - 1) * (X[i + 1] - X[i]);
    }
    return ret;
}

I've done some simple tests on this code (like the array {1,2,4,9} and {1,2,4,9,17}). Please let me know if you find any mistakes.

EDITED: I didn't read carefully the OP's definition and in my answer N denotes the array length just like k in the original question. Sorry for the inconvenience.

Answer 3

You can do this in a very simple way, O(n) time, and as mentioned in other answers, the abs function is redundant:

int ans = 0;

for (int i = 0; i < X.lengh; i++)
    ans += ((X.length - i) * (i)) * (X[i] - X[i-1]);

This method is based on the fact that X[i] - X[i-2] = 2(X[i] - X[i-1]) - (X[i-1] - X[i-2]), this allows you to just break every calculation and count the total amount of times the subtraction of two adjacent numbers in the array occur.

Answer 4

We can get rid of abs (array is sorted) and after that In the result x_1 appears (k-1) times as a negative, X_2 appears 1 time positive and k-2 times negative means totally we count it k-3 times negative and .... x_(k-1) appears k-3 times positive and x_k appears k-1 time positive so we have the following simplified summation:

int coef = 1-k;
int sum = 0;
for(int i=0;i<k;i++)
{
    sum += coef * x[i];
    coef += 2;
}

In the code I supposed the array is zero based index and x[0] equals to x_1 in my description.