100 Algorithm Challenge - Explained and solved- Algorithm 1(Easy)

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 x

abs(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 x

abs(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 x

abs(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