7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Vedran Šego Oct 19 '13 at 22:08
  • \$\begingroup\$ @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 \$\endgroup\$ – Sushim Mukul Dutta Oct 19 '13 at 22:48
13
\$\begingroup\$

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.

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

I would not give you the exact solution to this problem rather I would help you to get an intuition on how to solve this question.

If we try to generalize count of the number of times a particular number at index i is getting added and the number of times it is being subtracted then for every index i we can use that mathematically derived formula to compute the sum of contributions of every number in the absolute difference in O(N) time and O(1) extra space.

You can refer to this video if you still find difficulties in understanding this concept.

Video Link:-

https://youtu.be/A4sz4kNDa-8

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer @Vaibhav! And welcome to Stack Exchange. But let's not open ~7 years old threads, unless the question is unanswered or you have something more valuable to add to which is missing. Might I suggest to re-read answering guide. Cheers. :) \$\endgroup\$ – Sushim Mukul Dutta Jun 16 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.