Sum of Absolute Differences

ArrayMathPrefix Sum

Given a sorted array of distinct integers, create an array where each element i is the sum of the absolute differences between the number at index i in the original array and every other number in the array.

Example 1

Input

[
  1,
  2,
  3
]

Output

[4, 2, 4]

Explanation. For index 0 (element 1): |1-2| + |1-3| = 1 + 2 = 3; For index 1 (element 2): |2-1| + |2-3| = 1 + 1 = 2; For index 2 (element 3): |3-1| + |3-2| = 2 + 1 = 3. Output array is [3, 2, 3].

Example 2

Input

[
  -10,
  0,
  10
]

Output

[20, 20, 20]

Explanation. Each element has a total difference of 20 with all other elements.

Example 3

Input

Output

[111, 107, 93, 19]

Explanation. Calculating absolute differences for each element results in the output sums: 111 for index 0, 107 for index 1, 93 for index 2, and 19 for index 3.

Follow-up: Can the problem be solved in linear time complexity, considering the array is already sorted?

Constraints:

The input array will contain at least two elements and will not exceed 1,000 elements. Each element in the array is between -1,000,000 and 1,000,000.

Views: 3