A sorted list of $\mathbf N$ numbers is given.

$X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$

Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following value is minimised.

$$\sum_{1 \le i \lt j \le k} |(Y_i-Y_j)| $$ Let's call it FORMULA.

  • My Approach

I Select them such that $Y_1$ $\le$ $Y_2$ $\le$ $Y_3$ $\le$ ..... $\le$ $Y_K$ . Now we need to minimize

$$\sum_{1 \le i \lt j \le k} (Y_i-Y_j) $$


I m only considering $\mathbf K\,consecutive$ elements(could start from any position).

So, is it possible that the left out cases(i.e K non-consecutive elements ) give a lower value(for the formula above) than the cases i consider ?

  • Bonus Question

To calculate the FORMULA for a particular case $\;Y_1$ $\le$ $Y_2$ $\le$ $Y_3$ $\le$ ..... $\le$ $Y_K$

I create another list with $Z_j$= $(Y_{j+1} - Y_j) $ ---> Equation1

FORMULA = $\sum_{i=1}^{(n-1)}i(k-i)Z_i$ ---> Equation2

Is this Correct?

  • EDIT 1

In my opinion , If there are such instances, they would consist of equal elements in the original list with N numbers.

  • 3
    $\begingroup$ possible duplicate of Minimisation of a distance sum covering the REAL DOUBT $\endgroup$ Oct 22, 2013 at 16:11
  • 1
    $\begingroup$ The bonus question formula is not correct. If all the gaps are the same size, it would be correct without the $(k-i)$ term $\endgroup$ Oct 22, 2013 at 16:15
  • $\begingroup$ @RossMillikan could u give an exmaple where it fails? For List Y -10,20,30,40 (K=4) formula gives 100 . which is correct i think. $\endgroup$
    – PleaseHelp
    Oct 22, 2013 at 16:25
  • 1
    $\begingroup$ Your edit to Equation 1 has not solved the problem. On the right side $j$ is a dummy variable, so the value does not depend on $j$. $\endgroup$ Oct 22, 2013 at 17:58
  • 1
    $\begingroup$ Yes, that is fine $\endgroup$ Oct 23, 2013 at 7:57


You must log in to answer this question.

Browse other questions tagged .