Geek Answers Handbook

Absolute distance from various points in O (n)

I doubt. Part of the question requires calculating the sum of the absolute distance of a point from different points. | x - x1 | + | x - x2 | + | x - x3 | + | x - x4 | ....

I need to calculate this distance in O (n) for each point iterating in an array, for example:

array = {3,5,4,7,5}
sum of distance from previous points

dis[0] = 0; dis[1] = |3-5| = 2 dis[2] = |3-4| + |5-4| = 2 dis[3] = |3-7| + |5-7| + |4-7| = 9 dis[4] = |3-5| + |5-5| + |4-5| + |7-5| = 5

Can anyone suggest an algo to do this? An algorithm smaller than O (n ^ 2) will be evaluated (not necessarily O (n)).

Code for O (n ^ 2)

 REP(i,n){ LL ans = 0; for(int j=0;j<i;j++) ans= ans + abs(a[i]-a[j]) dis[i]=ans; }
+7
c algorithm graph dynamic-programming distance
source share
2 answers

O (n log n) is possible.

Suppose we had a data structure for a list of supported numbers:

 Insert(x) SumGreater(x) SumLesser(x) Insert(x) inserts x into the list. SumGreater(x) gives the sum of all elements greater than x, which are in the list. SumLesser(x) gives the sum of elements < x. NumGreater(x) gives the number of all elements greater than x. NumLesser(x) gives the number of all elements < x.

Using balanced binary trees with summable subtrees sums and subtrees counts stored in nodes, we can implement each operation in O (log n).

To use this structure for your question.

Go through the array from left to right and when you meet a new element x

You are asking for numbers already inserted for SumGreater(x) = G and SumLesser(x) = L and NumGreater(x) = n_G and NumLesser(x) = n_L

The value for x will be (G - n_G*x) + (n_L*xL) .

Then you insert x and continue.

+4
source share

Is O (n) possible? - If the size of your output is 1/2 * n ^ 2, how can you fill it in O (n) time?

+2
source share

More articles:


All Articles