×

# Faster alternative of this

 0 for(i=0;i

 2 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 :) answered 29 Sep '17, 02:00 82●6 accept rate: 0% I don't think it requires $s[i] \ge 0$. Same for @we7d also. (29 Sep '17, 02:07) meooow ♦6★ I agree with @meooow because we are using abs (29 Sep '17, 02:09) now that I think about it , yeah it does not require s[i] >=0 .. I guess I was just being too cautious :p (30 Sep '17, 00:06)
 1 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] answered 28 Sep '17, 09:22 2★we7d 22●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×4

question asked: 27 Sep '17, 23:02

question was seen: 270 times

last updated: 30 Sep '17, 00:07