How to Quickly Calculate the Total Absolute

for (int i = 0; i < n; ++i) {
    total += 1LL * a[i] * (2 * i - n + 1);
}

Differences Over All Pairs (Without Brute Force!)

Hey everyone!

While solving a problem recently, I found a really useful trick for calculating the sum of absolute differences between all pairs in a sorted array.

Say you have a sorted array like:

a = [1, 3, 6]

You want to compute:

|1 - 3| + |1 - 6| + |3 - 6| = 2 + 5 + 3 = 10

Just loop through the array once and compute this. Much faster than brute force!

Why This Works (Simple Explanation)

Let’s understand this in plain English — no complex math needed!

Each number in the array: - Will be subtracted from numbers after it. - Will subtract numbers before it.

So every number is: - Subtracted from n - 1 - i elements after it. - Added to i elements before it.

This means the net effect of a[i] is: ~~~~~ a[i] * (i — (n — 1 — i)) = a[i] * (2i — n + 1) ~~~~~

You just loop through the array and apply that for each element.

Example

Let’s try with a = [1, 3, 6]:

You just loop through the array and apply that for each element.

Example

Let’s try with a = [1, 3, 6]: ~~~~~ i = 0 → 1 * (20 — 3 + 1) = 1 * (-2) = -2 i = 1 → 3 * (21 — 3 + 1) = 3 * 0 = 0 i = 2 → 6 * (2*2 — 3 + 1) = 6 * 2 = 12

Sum = -2 + 0 + 12 = 10 ~~~~~

sort(a.begin(), a.end());
long long total = 0;
for (int i = 0; i < n; ++i) {
    total += 1LL * a[i] * (2 * i - n + 1);
}