All the Gaps — Solution & Editorial

Back to the Problem

Sort; element x at sorted index i (0-based) contributes x·i − (sum of everything before it). One pass with a running sum.

Complexity: O(N log N)

Watch out: ~10¹³ at the limits — 64-bit.