**PROBLEM SETTER** -

ZCO 2013

**DIFFICULTY** –

Easy

**PREREQUISITES** –

Sorting

**FIRST SUBTASK SOLUTION** –

A simple brute for iterating on all the C(N,2) combinations can do the task easily for N<5000, by taking the sum of difference of all pairs of elements.

int ans=0; for(int i = 1;i < n+1;i++) for(int j = i+1;j < n+1;j++) answer += abs(a[j]-a[i]); cout << answer;

**TIME COMPLEXITY** -

O(N^2)

**KEY OBSERVATIONS** –

- Sorting the array will not cause any change to the answer as the answer does not depend on the indices of the elements.
- Let us define a function diff(i), which denotes the sum of difference between a[i] and a[j] for all (i,j) where a[j] < a[i]. After sorting in ascending order, the above condition of a[j] < a[i] changes to j < i.

Mathematically, after sorting, diff(i) = $ \sum_{j=1}^{i-1} \hspace{2mm} ( a[i] - a[j] ). \hspace{2mm} $Now,

The above mathematical formula clearly defines dependency of diff(i) upon diff(i-1). Consequently, the transition from i to i+1 is in O(1) time. The answer we need is summation of diff(i) for all i. Don’t forget that this observation is valid only after the array is sorted.

**SECOND SUBTASK SOLUTION** –

We first sort the array in ascending order in accordance with observation 1. We have to iterate on the sorted array and maintain 2 variables – answer and diff_i.

sort(a+1,a+n+1); ll answer=0,diff_i=0; a[0] = 0; for(ll i=1;i < n+1;i++) { diff_i += (i-1)*(a[i]-a[i-1]); answer += diff_i; } cout << answer;

As we iterate, diff(i) can be updated in O(1) time using the formula in observation 2. answer can be maintained by adding the value of diff(i) to it after updating diff(i).

**Time Complexity** –

O(N * log(N))