Calculating sum of all the distance

Question

I have been given n points on a line with their locations. I need to sum of distances between each pair of points. Is it possible to do with complexity O(n).

Example: Given three points with their coordinates a(-1), b( -3), c(3). Required Sum: |-1 + 3| + | - 1 - 3| + |-3 - 3 | = 12

Please help me.

Answer 1

1. Compute length of each sequental segment:

   for (int i=0;i<n-1;i++) len[i]=x[i+1]-x[i];
   

Note this is for sorted points. If not, sort before computing sequental segments length.

2. Compute how many times each segment occurs in different pairwise distances: for some segment the number of pairs is leftSidePoints*rightSidePoints. In other words you computing contribution of each segment length in total sum.

    for (int i=0;i<n-1;i++) contributionOfSegment[i]=len[i]*(i+1)*(n-i-1);
   

   i+1 is leftSide points, n-i-1 is rightSide points for i-th segment

3. Answer is the sum of contribution of all segments:

    int sum=0; for (i=0;i<n-1;i++) sum+=contributionOfSegment[i];
   

UPDATE

Almost O(N) algo, nor O(Nlog(N)) (std sort), nor O(maxX) (computing sort). Complexity is O(N)loglog(maxX)) or saying simpler O(N)*number_of_bits_in_maxX which is 5N for 32 bit integers which is almost linear.

Main logic remains as I descibed above. Bottleneck point is sorting - and O(N)*number_of_bits_in_maxX factor is sorting step. We will sort array with Van Emde Boas tree. That tree supports findNext(x) operation - find next element after x with complexity O(loglogmaxX). Insert also has complexity O(loglogmaxX).

So, Van Emde Boas sorting looks like:

1. populate tree in O(N)*number_of_bits_in_maxX via for(i=0;i<n;i++) tree.insert(x[i]) where x is unsorted input array.
2. Find min in O(N) in unsorted array
3. sortedArray[0]=min
4. for(int i=1;i<n;i++) sortedArray[i] = tree.findNext(sortedArray[i-1])

Then, use my logic above, just replace arrays: x to sortedArray

Note that VEBTree sorting interesting only in theory, in practice it may have hidden constant factor and for small N, log(N) may be better than loglog(maxX) and thus, standart sorting may be faster than tree sorting. VEBTree will be cool if N is extremely large while maxX is just 32 or 64 bit integer.

Answer 2

There is a possible solution in linear order time, irrespective of points being sorted or unsorted. So, let's start with points n+1 unsorted points. As given, the points are along a line (let's say x-axis) and they have integral x-values only. Let's say the first point is P0 and the last one is Pn. It implies that total points are n+1 and total point-wise distances are n.

1. Iterate through the points to find the minimum (minX) and maximum (maxX) x values;
2. Create an array of bits (called BitArray[max - min + 1]);
3. Iterate again through the points and for every point you encounter, set BitArray[minX + currentX] = true;
4. Now create another int Distances[n] array and start iterating through all values in BitArray.
   1. The first bit would be true as it will represent the point minX;
   2. Find the next true bit and set Distances[0] = thisX - minX;
   3. This way, populate all the consecutive distances into the Distances array.

Until now, the run time complexity is O(maxX - minX), which is linear. For points close enough, this will be O(n). Also, we have created an array that tells us the distance between (P0, P1) at index 0, between (P1, P2) at index 1, between (P2, P3) at index 2 and so on.

The arrangement of points along x-axis will look like this (dashed line is x-axis and each * is a point, dn is distance between P(n-1) and Pn),

---*----------*------*--------*---------....--------*---
   ^          ^      ^        ^                     ^
   P0  (d0)  P1 (d1) P2 (d2)  P3  (d3)  ....  d(n)  Pn

Now, the calculation is O(n). Just one simple summation.

The summation is:

(1 * (n - 1) * Distances[0]) +
(2 * (n - 2) * Distances[1]) + 
(3 * (n - 3) * Distances[2]) +
.
.
.
(1 * (n - 1) * Distances[n-1])

---

How I arrived at that summation

Take P0. The sum of P0's distance from P1 to Pn

= d(P0, P1)  + d(P0, P2)     + ... + d(P0, Pn)
= d[0]       + (d[0] + d[1]) + ... + (d[0] + d[1] till d[n-1])
= (n-1)*d[0] + (n-2)*d[1]    + ... + (n-1)*d[n-1]

This same way we take P1 and calculate its distance from P2 to Pn

Then take P3... till finally considering only distance between P(n-1) and Pn

On summing these distances, we straight forward get the formula I mentioned above.

---

Hence, if points are given sorted, running time is O(n) and if points are given unsorted, running time is O(maxX - minX) which is still linearly growing.

Answer 3

I can think of a way if the points are sorted. Assume we have n points. Let's consider two adjacent points, Pi and Pi+1, Let's assume the distance between Pi and other Points is Di, Distance between Pi and Pi+1 is d, Then Di+1 = Di + i * d - (n - i - 1) * d, Then we can calculated the distances from a point to all the other points in O(1) if the distances from its left adjacent point to all the other points are known. We only need to calculated the first point, and update accordingly.

The logic of the equation is that, when move from Pi to Pi+1, all the distances from Pi+1 to all the points on its left are increased by d, the distances from Pi+1 to all the points on its right are decreased by d.

Answer 4

This is doable if the points are in sorted order. Let's take a simple example, bigger than n=3 since n*(n-1)/2 (all possible pairs without duplicates where (a,b) and (b,a) are considered duplicates) in such case is also 3 and is misleading:

n = 4 // number of points
p = [-3, -1, 1, 3] // our points

We will calculate all distances from the first point p[0] first, this is an O(n) operation and will yield 12 as a result because |-3 + 1| + |-3 - 1| + |-3 - 3| = 2 + 4 + 6 = 12.

We observe now that since the points are on a line and that the next point will be to the right of the first point, so we can calculate all the distances by simply subtracting the distance between the current and previous point from the previous points sum which would look accordingly:

12 - (k - 1) * dist = 12 - (4 - 1) * 2 = 12 - 6 = 6

Since the distance between point 0 and 1 is equal to 2 and we need to subtract this value for each previously calculated distance (the previous point was part of k-1=3 pairs). In the next iteration k will be 1 smaller:

6 - (k - 1) * dist = 6 - (3 - 1) * 2 = 6 - 4 = 2

So in the end the initial summation will be O(n) and then we will have to do O(1) n-times which yields O(n).

This would yield us an array of partial sums [12,6,2,0]=20, you don't need to store it, just to visualize it.