2

I have a list of non repeating positive integers $(a_1,\dots,a_n)$. I need to find integers $x, y$ such that the value of $\sum_{i=1}^n\min\{|a_i-x|,|a_i-y|\}$ is minimal.

For example:

  1. If $a = [2,3,6,7]$ (my list of numbers) then $x$ and $y$ for this list are $3$ and $7$, as:

    $|2-3| + |3-3| + |6-7| + |7-7| = 2$ which is the minimum value of the expression.

  2. If $a = [1,3,5]$ then $x$ and $y$ for this list are $1$ and $4$ as:

    $|1-1| + |3-4| + |5-4| = 2$ which is the minimum value of the expression.

What is the best approach to find these two integers $x$ and $y$ given that my list of numbers will only contain positive integers?

Sarvesh Ravichandran Iyer
  • 76,105
Rick
  • 21
  • 2
    Please do not link to images. Instead, use MathJax to write the formula that appears in the image. It will make your question much easier to read – Moko19 Aug 07 '22 at 16:02
  • Formulas as image links also attract close votes like crazy. – JonathanZ Aug 07 '22 at 16:48
  • Can you answer the question if you only get to choose one integer $x$? Have you seen the proof that this is optimal? This question is harder, but the other will give some insight. You are going to divide your list into the bottom and top and find one integer for each piece, which can apply the previous question. – Ross Millikan Aug 08 '22 at 03:00

0 Answers0