Problem - AbsoulteValuesSumMinimization
Given a sorted array of integers a, find an integer x from a such that the value of
abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)
is the smallest possible,If there are several possible answers, output the smallest one.
Example
For a = [3, 5, 9], the output should be
absoluteValuesSumMinimization(a) = 5.
For a = [2, 4, 7, 6], the output should be
absoluteValuesSumMinimization(a) = 4.
For a = [2, 4, 7, 6, 6, 8], the output should be
absoluteValuesSumMinimization(a) = 7.
Understanding the problem
- abs stands for absolute.
Simply above problem states, we have to pick a
number (x) from sorted array (a) so that if we sum the
absolute of difference of every element in a array with x,
that sum number will be minimum as compare to every other x.
Explaining the english with example
a = [3, 5, 7]
First we pick x, lets pick every element
let x = a[0] = 3;
lets calculate the abs of difference of every element with xabs(a[0]-x) + abs(a[1]-x) + abs(a[2]-x)
abs(3-3) + abs(5-3) + abs(7 - 3) => 0 + 2 + 4 => 6
we got 6 by picking x as 3.a = [3, 5, 7]
Now let x = a[1] = 5;
lets calculate the abs of difference of every element with xabs(a[0]-x) + abs(a[1]-x) + abs(a[2]-x)
abs(3-5) + abs(5-5) + abs(7 - 5) => 2 + 0 + 2 => 4
we got 4 by picking x as 5.Now let x = a[2] = 7;
lets calculate the abs of difference of every element with xabs(a[0]-x) + abs(a[1]-x) + abs(a[2]-x)
abs(3-7) + abs(5-7) + abs(7 - 7) => 4 + 2 + 0 => 6
we got 6 by picking x as 7.
So Hope you understood the problem, In the above case, the number which yeilds minimum result is the absoluteValuesSumMinimization i.e 5,
_Oh! Wait, Wait, Wait... But this thing has a name which we all understand.... *MEAN Value_*
Yup that is mean value
Okay lets Solve it !! Using TS Code
Algorithm
To find mean value array must be sorted, which is in our case
Next we find if total numbers of element in array are even or
odd,On dividing with 2, if even then we have two mean values, we > take the smaller one, if odd then there is only one mean value.if odd then we will get the value in fraction,
Math.floor() to rescueeee !!
TS Code
Okay! Lets code.
function absoluteValuesSumMinimization(a: number[]): number {
//Find if the total numbers are ever or not.
const isEven = a.length % 2 === 0;
return isEven ? a[a.length / 2 - 1] : a[Math.floor(a.length / 2)];
}
Dry Run (Testing)
a = [3, 5, 7]
absoluteValuesSumMinimization(a);
isEven = 3 % 2 = 1 === 0 => False
then,
the false part of the statement return will run,
a[Math.floor(1.5)] => a[1] => 5
returns 5;
so the mean is 5
Okay thats it, Thank you.
Keep Coding.
Refrence
This is the course I am taking on udemy, I am writing these series for my better understanding.
100 Algorithm Challenge Course
Top comments (0)