Problem Brief

Minimum Difference Sum

FULLTIMEOA

Given an array of n integers, rearrange them so that the sum of the absolute differences of all adjacent elements is minimized. Then, compute the sum of those absolute differences.

Function Description

Complete the function minDiff in the editor.

minDiff has the following parameter:

int arr[]: an integer array

Returns

int: the sum of the absolute differences of adjacent elements

1Example 1

Input

arr = [1, 3, 3, 2, 4]

Output

Explanation

If the list is rearranged as arr' = [1, 2, 3, 3, 4], the absolute differences are |1 - 2| = 1, |2 - 3| = 1, |3 - 3| = 0, |3 - 4| = 1. The sum of those differences is 1 + 1 + 0 + 1 = 3.

Constraints

Limits and guarantees your solution can rely on.

2 ≤ n ≤ 10^5
0 ≤ arr[i] ≤ 10^9, where 0 ≤ i < n

Draft autosaves locally

public int minDiff(int[] arr) {
    // write your code here
}

Input

arr

[1, 3, 3, 2, 4]

Output