Faster alternative of this

general
1

for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
rev=rev+abs(s[i]-s[j]);
}
}

2

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
3

you can proceed as follows :
( considering number of elements = n and array indexes starting at 0)

  1. 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 )
  2. 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 :

  1. 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
  2. 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 :slight_smile:
2 Likes
4

I don’t think it requires s[i] \ge 0.
Same for @we7d also.

5

I agree with @meooow because we are using abs

6

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