w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Find an efficient algorithm in terms of reduce Big O complexity

If you sort the elements first, you can get the runtime down to O(n log n).

The idea here is that if a[] is the list of integers in sorted order and b[i] is the sum of the differences between a[i] and the other numbers, then b[i+1] can be computed directly in terms of b[i], i, a[i+1] - a[i], and the length of the array.

I won't say exactly how, but here's a hint. How much can Math.abs(a[i+1] - a[j]) differ from Math.abs(a[i] - a[j])? For which j is Math.abs(a[i+1] - a[j]) greater? For which j is it smaller?

Now, after you compute those, the b[i]s then among themselves contain each difference twice. The value you want is just their sum divided by 2.





© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.