748. The Distance From Each Value to All the Others
A NON DECREASING array is given. For each position i, print the sum of |a[i] - a[j]| over
every other position j.
2 3 5 -> 4 3 5
1 4 6 8 10 -> 24 15 13 15 21
0 5 10 -> 15 10 15
## Sortedness removes the absolute value
Because the array is non decreasing, every value to the LEFT of i is at most a[i] and every
value to the RIGHT is at least a[i]. So the absolute value can be dropped in each direction
with a known sign:
left contribution = sum over j < i of (a[i] - a[j]) = i * a[i] - P[i]
right contribution = sum over j > i of (a[j] - a[i]) = (P[n] - P[i+1]) - (n - 1 - i) * a[i]
where P is the prefix sum array. The answer at i is the two added together.
Turning an absolute value into two sign-known halves, using an ordering the input guarantees, is the idea. Without sortedness there is no way to split the sum at all and the problem is genuinely quadratic.
## Counting how many terms are on each side
There are exactly i values to the left and n - 1 - i to the right. Those counts multiply
a[i], and getting either wrong shifts the whole answer.
n - i instead of n - 1 - i is the classic slip: it counts a[i] itself as being to its own
right, which subtracts one extra a[i] and leaves every printed answer short by exactly
a[i]. On an array where every value is equal the correct answer is all zeros and the slip
prints -a[i] instead, so an all-equal test catches it, but ONLY if the repeated value is not
zero. 0 0 0 prints all zeros either way, while 1 1 1 1 and 3 3 3 3 3 expose it, which is
why both are in the set.
## Why P[i] and P[i+1] and not one of them twice
P[i] is the total of everything strictly before i. P[n] - P[i+1] is the total of
everything strictly after it. The element itself appears in neither, which is what the statement
asks for.
## Boundaries
A single value answers 0, since there is nothing to compare against. Position 0 has an empty
left side and position n-1 an empty right side, and both fall out of the formula without a
special case.
## Overflow
10^5 values up to 10^9 give a total of 10^14, and i * a[i] alone reaches
10^14. Every intermediate needs 64 bits.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 10^9` - the values are given in non decreasing order
Input
The first line contains an integer n.
The second line contains n integers in non decreasing order.
Output
Print n integers on one line, separated by spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.