CODEWITHSUNDEEP
algorithmmathcomputer-science
agassaa
agassaa

Reputation: 145

find a number for minimum sum of absolute difference in an array

for example, array a[]= {1,1,10}, we need to find 'x' such that |x-1|+|x-1|+|x-10| is minimum.
here, x is 1.

Could it be solved in greedy approach, like taking average or something else?
Note: taking average doesn't work, why?

I can only come up with O(nlogn) solution (binary search), is there any other approach like dp?

Thanks in advance!

Upvotes: 3

Views: 2242

Answers (1)

Ilja
Ilja

Reputation: 2114

This is a very simple question (don't feel offended: at least, the answer is simple if you know it):

If you have an odd number of items, then the one in the middle will be your optimum.

If you have an even number, any number between the central two will be equally optimal.

So no numerical calculation is needed, only sorting :)

Explanation: to move your resulting number will change each of the abs(x-x1) by the same amount, but with different signs: some increasing and some decreasing.

From the point in the center (in the odd case) there will be one more increasing abs when moving in either direction; while when moving between the two central points (in the even case) there will be equally many abs of each sign.

Upvotes: 6

Related Questions