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
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-s[n-1]) + (n-3)*(s - s[n-2]) + (n-5)*(s - 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
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
I don’t think it requires s[i] \ge 0.
Same for @we7d also.
I agree with @meooow because we are using abs
now that I think about it , yeah it does not require s[i] >=0 … I guess I was just being too cautious