for(i=0;i<n;i++)

{

for(j=i+1;j<n;j++)

{

rev=rev+abs(s[i]-s[j]);

}

}

if s[i]>=0, you can sort then use prefix sum

for(int i=n-1;i>0;i–)ans+= i *v[i] +pref[i-1]-pref[0]

1 Like

you can proceed as follows :

( considering number of elements = n and array indexes starting at 0)

- sort the array in descending order , so that abs(s[i] - s[j]) = (s[i] - s[j]) for j > i ( This takes O(nlogn) time )
- find the sum of following series :

(n-1)*(s[0]-s[n-1]) + (n-3)*(s[1] - s[n-2]) + (n-5)*(s[2] - s[n-3]) + ...

This will get you to O(nlogn) from O(n^2)

Note that the last term will become zero if the number of items is odd , this is not a problem

Explanation :

If you sort the array and write down the sum terms and get rid of the brackets , you will see that :

- largest number occurs (n-1) times as positive and 0 times as negative. smallest number occurs (n-1) times as negative and never as positive
- second largest number occurs (n-2) times as positive and 1 time as negative , and so on and so forth.

Adding it all up , it forms the series I wrote above.

I hope I was of help

2 Likes

now that I think about it , yeah it does not require s[i] >=0 … I guess I was just being too cautious