CODEWITHSUNDEEP
javascriptalgorithmmath
TOreilly
TOreilly

Reputation: 145

Explaining the math behind an algorithm

Given a sorted array of integers a, find such an integer x that the value of

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x) is the smallest possible (here abs denotes the absolute value). If there are several possible answers, output the smallest one.

Example

For a = [2, 4, 7], the output should be absoluteValuesSumMinimization(a) = 4.

I was able to solve this by brute forcing it but then i came upon this

function absoluteValuesSumMinimization(A) {
    return A[Math.ceil(A.length/2)-1];
}

looking to learn how/why this works.

Upvotes: 14

Views: 2789

Answers (3)

danbanica
danbanica

Reputation: 3038

Let's assume that we have n1 values where a[i] - x is negative and n2 values where a[i] - x is positive.

If we increase the integer x by one, then the sum of the absolute values increases by n1 - n2.

If we decrease the integer x by one, the total sum of the absolute values increases by n2 - n1.

Therefore, as long as n1 and n2 are not equal, we can decrease the total sum of absolute values by moving x in one direction or the other, depending on whether n1 - n2 is positive or negative.

Thus, at the minimum it is necessary to have n1 = n2, i.e. there need to be same as many a[i] values smaller than x as there are larger than x.

Upvotes: 0

Lanno
Lanno

Reputation: 44

We can write the problem as follows:

https://i.sstatic.net/1IFXP.jpg

When we factor out the N, the first term becomes the average of the list "a":

N (mean(a) - aj)

If we assume that the list of sorted, then the value that will minimize this quantity is the value that is closest to the term mean(a), which is the median of the list.

Math.ceil(A.length/2)-1 simply returns the middle value of the list, which is the median of a sorted list.

Upvotes: 1

Arnav Aggarwal
Arnav Aggarwal

Reputation: 789

Let's break it down.

A.length/2 returns half the length, used to find the middle of the array. For even-length arrays, this will be to the right of the middle. For odd-length arrays, it'll be the middle.

Math.ceil(A.length/2) rounds up if necessary, so the middle of an array of 5 would be 2.5 -> 3. This makes the odd-length arrays off by one.

Math.ceil(A.length/2)-1 goes down one index. This corrects off-by-one errors for all the arrays.

All this solution is saying is that in an array of even length, the value you're looking for will always be to the left of the middle. In an array of odd length, it will always be the middle item.

This makes sense intuitively. Subtracting the middle item in the array from each item will always result in the lowest sum. In an even length array, the two center items will always result in an identical sum, so the lowest number will be to the left of the center.

To see this, remove the console.log comment from this brute-force solution and try several 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)];
}

Upvotes: 5

Related Questions