Explanation of the math behind the algorithm
Given a sorted array of integers a, find an integer x such that the value
abs (a [0] - x) + abs (a [1] - x) + ... + abs (a [a.length - 1] - x) is the smallest (here abs denotes an absolute value). If there are several possible answers, print the smallest one.
Example
With a = [2, 4, 7], the output should be absoluteValuesSumMinimization (a) = 4.
I was able to solve this by rough forcing, but then I came across this
function absoluteValuesSumMinimization(A) {
return A[Math.ceil(A.length/2)-1];
}
to see how / why it works.
source to share
Let's break it down.
A.length/2
returns half the length used to find the middle of the array. For even-sized arrays, this will be to the right of the middle. For arrays of odd length, this will be the middle.
Math.ceil(A.length/2)
rounds if necessary so that the middle of an array of 5 is 2.5 -> 3. This makes arrays of odd lengths off by one.
Math.ceil(A.length/2)-1
goes down one index. This fixes errors in one go for all arrays.
This whole solution says that in an array of even length, the value you are looking for will always be to the left of the middle. In an array of odd length, it will always be the average.
This makes sense intuitively. Subtracting the middle element in the array from each element will always result in the lowest sum. In an array of equal length, the two center elements will always have the same sum, so the lowest number will be to the left of the center.
To see this, remove the comment console.log
from this brute-force solution and try multiple arrays:
function absoluteValuesSumMinimization(ints) {
const vals = [];
ints.forEach(int => {
const sum = ints.reduce((accum, next) => {
return accum + Math.abs(next - int);
}, 0);
vals.push(sum);
});
// console.log(vals);
const lowest = Math.min(...vals);
return ints[vals.indexOf(lowest)];
}
source to share
Suppose we have n 1values, where is a[i] - x
negative and n 2values where a[i] - x
positive.
If we increase the integer x
by one, then the sum of the absolute values will increase by n 1 - n 2...
If we decrease the integer x
by one, the total sum of the absolute values will increase by n 2 - n 1...
Therefore, while n 1 and n 2are not equal, we can decrease the total sum of the absolute values by moving x
in one direction or the other, depending on whether n 1 - n 2 positive or negative.
Thus, at least it is necessary to have n 1= n 2, i.e. must be the same number as the number is a[i]
less x
since they are greater than x
.
source to share
We can write the task like this:
When we factor N, the first term becomes the mean of the list "a":
N (average (a) - a j)
Assuming the list is sorted, then the value that minimizes this value is the value that is closest to the mean (a), which is the median of the list.
Math.ceil (A.length / 2) -1 simply returns the average of the list, which is the median of the sorted list.
source to share