Given an array, find the product of the absolute difference of every pair of integers.
For example: Given a[]= {2,3, 5, 7 };
output would be (3-2) * (5-2) * (7-2) * (5-3) * (7-3) * (7-5) = 240.
Can it be done better than O(n^2) ? Edit: All elements are distinct.
If you had to compute the sum of the absolute differences, then this would be your solution
Basically, if you take an arbitrary number, let's name it x, then you have it
m * x - n * x,
where m is the number of items which are smaller than x and n is the n number of items, which are greater than x. So, if for some reason you had a sorted array, then the index of each item would directly tell you how many greater or smaller items are if it's unique in the array. If not, then you can determine the number of higher and lower elements as well.
So, if the array is sorted, than computing the result is linear. Sorting the array if it's completely unsorted is n * log(n) of complexity if you use mergesort. Hence, the complexity is
O(n + n * log(n)) = (n + 1)log(n)
But for the product of absolute differences
you have a product of the form of
(a1 - b1) * ... (...)
since you have a product of subtractions, in order to find a pattern that you could use to optimize, you need more information about your data. The input that you have seem to contain primes. The product of
(a1 - b1) * (a2 - b2)
is
a1a2 - a1b2 - b1a2 + b1b2
I do not know about any pattern that you could use for your optimization, so I think this has an O(n^2) complexity.
