Subtracting Sorted Data

Question

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

I 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 get the correct answer using the above solution, but it is not optimized. In some cases, the time limit is exceeded. Is there any algorithm for implementing this with minimal complexity?

Answer 1

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

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

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

This can be divided into two amounts:

 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 the general case, Xj appears j-1 therefore it contributes (j-1)Xj to the amount (subject to indexing based on 1).

In the same way, Xi appears in the second sum (ki) times, so it contributes (ki)Xi to the total.

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

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

This computes 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 exists X _i ≤ X _j .

And designate the purpose 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 ) + ...

Note

Σ _{k ≤ i ≤ N} | X _i - X _k

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

So, to calculate the sum, we have the following iteration:

 /* * 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 did some simple tests for this code (for example, an array of {1,2,4,9} and {1,2,4,9,17}). Please let me know if you find any errors.

EDITED: I have not read the definition of OP carefully, and in my answer, N denotes the length of the array just like k in the original question. Sorry for the inconvenience.

Answer 3

You can do this very simply, 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 simply break down each calculation and calculate the total number of times when two adjacent numbers in the array are subtracted.

Answer 4

We can get rid of abs (the array is sorted), and after that As a result, x_1 appears (k-1) times as negative, X_2 appears 1 times positive and k-2 times negative means that we consider it k-3 times negative and .... x_ (k-1) appears k-3 times positive, and x_k appears positive k-1, 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 assumed that the array is an index based on zero, and x [0] is equal to x_1 in my description.