absoluteValuesSumMinimization

0-problem.md

Given a sorted array of integers a, your task is to determine which element of a is closest to all other values of a. In other words, find the element x in a, which minimizes the following sum:

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)

(where 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.

for x = 2, the value will be abs(2 - 2) + abs(4 - 2) + abs(7 - 2) = 7. for x = 4, the value will be abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5. for x = 7, the value will be abs(2 - 7) + abs(4 - 7) + abs(7 - 7) = 8. The lowest possible value is when x = 4, so the answer is 4.

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

for x = 2, the value will be abs(2 - 2) + abs(3 - 2) = 1. for x = 3, the value will be abs(2 - 3) + abs(3 - 3) = 1. Because there is a tie, the smallest x between x = 2 and x = 3 is the answer.

Input/Output

[execution time limit] 4 seconds (py3)

[input] array.integer a

A non-empty array of integers, sorted in ascending order.

Guaranteed constraints:

1 ≤ a.length ≤ 1000,
-106 ≤ a[i] ≤ 106

[output] integer

An integer representing the element from a that minimizes the sum of its absolute differences with all other elements.

1-examples.txt

Input:
a: [2, 4, 7]
Expected Output: 4

Input:
a: [2, 3]
Expected Output: 2

Input:
a: [1, 1, 3, 4]
Expected Output: 1

Input:
a: [0, 7, 9]
Expected Output: 7

Input:
a: [23]
Expected Output: 23

Input:
a: [-10, -10, -10, -10, -10, -9, -9, -9, -8, -8, -7, -6, -5, -4, -3, -2, -1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
Expected Output: 15

Input:
a: [-4, -1]
Expected Output: -4

Input:
a: [-1000000, -10000, -10000, -1000, -100, -10, -1, 0, 1, 10, 100, 1000, 10000, 100000, 1000000]
Expected Output: 0

2-solution.md

for [a, c], if you go from a to a+1 you moved +1 futher from a, but -1 closer to c. So if you could pick any number you wanted, every number between [a, c] (inclusive) is just as good. However for this problem you need to pick one of the given, and on a match should pick the smallest, so you pick a.

[a, c] for choose any number => any number in the inclusive range [a, c] [a, c] for choose a given number => a or c [a, c] for choose a given number and choose smaller => a

Now moving to [a, b, c], the base case of [a, c] showed it doesn't matter what number you pick between [a,c] if you could pick any. In this case, b is guaranteed to be between a and c, so you pick "b" because b-b=0.

Extrapolating further: [a, b1, b2, b3, c]

From above, the best from just [a, c]'s pov is any of [b1, b2, b3]. Then if you find the best for [b1, b2, b3], you're back to the original cases, and as above you pick b2.

So the answer is always the center number, which is the median (or in this case, median low).