CODEWITHSUNDEEP
algorithmdynamic-programming
Thanatos
Thanatos

Reputation: 1186

Element that minimize the sum?

I found a problem that stated:

Let's consider a vector x = (x1, x2 ... xn) with real elements. 
1). Sort the vector  -- easy
2). Find a real number a so that sum ( abs (xi - a) ) is minim

I don't know if sorting the array helps, but for 2). I thought i can do the aritmetic sum of all elements in the vector and say that the avg is the a we were looking for.

But that isn't correct. Example:

x = (1, 10, 10)
avg = [ 21/3 ] = 7 = a
sum = |1 - 7| + |10 - 7| + |10 - 7| = 6 + 3 + 3 = 12

but if we consider a = 10 we get

sum = |1 - 10| + |10 - 10| + |10 - 10| = 9 < 12

Another solution I could think of would be a brute force from the min element to the highest with a step of i += 0.1

Upvotes: 4

Views: 224

Answers (1)

amit
amit

Reputation: 178451

You are looking for the median - rather then the average.

This is because what you are looking for is actually the geometric median - which happens to be the standard median if you have only one dimension (and you do).

The median can be found in O(n) using Selection Algorithm - so the sort is redundant.

Upvotes: 4

Related Questions